힙(Heap)구조에서 삽입과 삭제!

힙 : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 왼쪽부터 차례로 채운다 생각해면 됨

힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으려면, O(log n)이 걸림
• 우선 순위 큐와 같이 최대값 또는 최소값을 바르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

힙의 구조

• 최대 힙, 최소 힙으로 분류할 수 있다.
• 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.(최대힙경우)
• 완전 이진 트리 형태를 가진다
• 완전 이진 트리이기 때문에 수학적 패턴으로 배열을 활용할 수 있다

힙의 동작

데이터의 삽입
- 최하단(배열의 마지막)에 노드를 넣고 부모 노드보다 크면 자리를 바꿔주는 형식이다.
- 고로 루트 노드가 가장 큰 값이 되고, 자식 노드의 크기는 순서 없이 저장된다.
- 번외) 트리는 왼쪽 끝 자식 노드의 값이 가장 작고, 오른쪽 끝 자식 노드가 가장 크다.

• 데이터의 삭제
  • 보통 루트 노드를 삭제하는 것이 일반적(가장 큰 값을 삭제)
  • 상단을 제거하고 가장 하단부 왼쪽에 위치한 노드(배열의 마지막)를 루트 노드로 이동
  • 루트 노드의 값이 자식 노드의 값 중 보다 큰 것이 있는지 확인
  • 큰 것이 있다면 두개의 자식 노드 중 더 큰 것과 바꿔주는 것을 반복한다.
    

힙과 배열

• 일반적으로 힙 구현시 배열 자료구조를 활용함
• 배열은 인덱스가 0번부터 시작하지만, 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 수월함
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1
    

예) 10노드(인덱스=2)의 부모인덱스와 자식인덱스

부모 : 2//2=1, 왼쪽 자식 : 2*2 = 4, 오른쪽 자식 : 2*2+1 = 5

데이터 삽입하기

• 최하단(배열의 마지막)에 노드를 넣고 부모 노드보다 크면 자리를 바꿔주는 형식이다.
• 고로 루트 노드가 가장 큰 값이 되고, 자식 노드의 크기는 순서 없이 저장된다.
• 번외) 트리는 왼쪽 끝 자식 노드의 값이 가장 작고, 오른쪽 끝 자식 노드가 가장 크다.
  

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 0번인덱스를 지정함으로써 root인덱스는 1번이 됨
        self.heap_array.append(data) # root노드에 data삽입
        
    def move_up(self,insert_idx):
        if insert_idx == 1:
            return False
        
        parent_idx = insert_idx//2
        if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
            return True
        
        return False
        
        
    def insert(self, data):
        # 1 최하단(배열의 마지막)에 노드를 넣었음
        self.heap_array.append(data)

        insert_idx = len(self.heap_array) - 1 # 부모 노드를 파악하기 위해 현재 인덱스를 구함(-1은 None이 있기 때문)
        # 부모 노드보다 큰지에 대한 여부를 함수를 통해 판단하고 반복함
        while self.move_up(insert_idx):
            self.heap_array[insert_idx],self.heap_array[insert_idx//2] = self.heap_array[insert_idx//2],self.heap_array[insert_idx]
            insert_idx = insert_idx//2

heap = Heap(15)
heap.heap_array
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
print(heap.heap_array)
heap.insert(20)
print(heap.heap_array)

[None, 15, 10, 8, 5, 4]
[None, 20, 10, 15, 5, 4, 8]

데이터의 삭제

• 보통 루트 노드를 삭제하는 것이 일반적(가장 큰 값을 삭제)
• 상단을 제거하고 가장 하단부 왼쪽에 위치한 노드(배열의 마지막)를 루트 노드로 이동
• 루트 노드의 값이 자식 노드의 값 중 보다 큰 것이 있는지 확인
• 큰 것이 있다면 두개의 자식 노드 중 더 큰 것과 바꿔주는 것을 반복한다.
  

class Heap:
    def __init__(self,data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_down(self, popped_idx):
        
        # case 1. 부모의 자식 노드가 2개 있을 때
            # 설명을 붙이자면 popped_idx는 현재 부모 노드이다.
            # 배열의 길이가 왼쪽 자식 노드의 위치 보다 크다면?
            # 자식 노드는 2개이다
            # -1의 이유는 None이 처음에 포함됐기 때문이다.
        if len(self.heap_array)-1 > popped_idx*2:
            # 두개의 자식 노드 중 하나라도 부모보다 클 때 True를 반환하여 바꿔줄 수 있다.
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2] or self.heap_array[popped_idx] < self.heap_array[popped_idx*2 +1]:
                return True
        #case 2. 부모의 자식 노드가 1개 있을 때
        elif len(self.heap_array)-1 == popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2]:
                return True
        #case 3. 부모의 자식노드가 없을 때
            # 위에서 2개일 때와 1개일 때를 제외하면 없는 경우이다.
        return False
    
    def pop(self):
        # 루트 노드 삭제하기
        if len(self.heap_array) <= 1:
            return None
        # 빼줄 데이터(확인용)
        returned_data = self.heap_array[1]
        # 가장 마지막 데이터(배열의 마지막 데이터)와 루트 데이터를 바꿔준다.
        self.heap_array[1] = self.heap_array[-1]
        # 마지막 데이터를 삭제
        del(self.heap_array[-1])
        
        #루트 데이터를 뺐기때문에 루트 데이터의 인덱스는 1이다
        popped_idx = 1
        while self.move_down(popped_idx):
            # 자식 노드가 1개만 있을 경우(왼쪽만 있게 됨) 오른쪽 자식노드의 인덱스 값을 사용하면 에러가 나기에 try except구문 활용
            try:
                # 왼쪽 자식 노드가 클 경우
                if self.heap_array[popped_idx*2] > self.heap_array[popped_idx*2+1]:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2
                # 오른쪽 자식 노드가 클 경우
                else:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2+1]=self.heap_array[popped_idx*2+1],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2 + 1
            # 자식 노드가 하나 일 경우(왼쪽 자식만 있음)
            except IndexError:
                self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                popped_idx = popped_idx*2                
        return returned_data

print(heap.heap_array)
heap.pop()
print(heap.heap_array)

[None, 20, 10, 15, 5, 4, 8]
[None, 15, 10, 8, 5, 4]

합친 코드(주석x)

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_up(self,insert_idx):
        if insert_idx == 1:
            return False
        
        parent_idx = insert_idx//2
        if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
            return True
        
        return False
        
    def insert(self, data):
        self.heap_array.append(data)
        insert_idx = len(self.heap_array) - 1
        
        while self.move_up(insert_idx):
            self.heap_array[insert_idx],self.heap_array[insert_idx//2] = self.heap_array[insert_idx//2],self.heap_array[insert_idx]
            insert_idx = insert_idx//2
            
    def move_down(self, popped_idx):
        if len(self.heap_array)-1 > popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2] or self.heap_array[popped_idx] < self.heap_array[popped_idx*2 +1]:
                return True
        elif len(self.heap_array)-1 == popped_idx*2:
            if self.heap_array[popped_idx] <self.heap_array[popped_idx*2]:
                return True

        return False
    
    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        del(self.heap_array[-1])
        
        popped_idx = 1
        while self.move_down(popped_idx):
            try:
                if self.heap_array[popped_idx*2] > self.heap_array[popped_idx*2+1]:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2
                else:
                    self.heap_array[popped_idx],self.heap_array[popped_idx*2+1]=self.heap_array[popped_idx*2+1],self.heap_array[popped_idx]
                    popped_idx = popped_idx*2 + 1

            except IndexError:
                self.heap_array[popped_idx],self.heap_array[popped_idx*2]=self.heap_array[popped_idx*2],self.heap_array[popped_idx]
                popped_idx = popped_idx*2
                
        return returned_data

이미지 출처 : 잔재미코딩