[자료구조] 힙(Heap) 연산 - 삽입/추출 구현하기 (Python)

• 힙(Heap)

: 힙의 특성* 을 만족하는 거의 완전한 트리(Almost Complete Tree)인 특수한 자료구조

* 힙의 특성: 최소 힙(Min Heap)에서는 부모가 항상 자식보다 작거나 같음

 

: 우선순위 큐의 heapq 모듈이 힙으로 구현됨 (heapq.heappush() 및 heapq.heappop())

: 우선순위 큐는 힙으로 만들어지며, 힙은 배열로 만들어지지만 항상 정렬된 구조를 갖지 않음 

 

 

 

: 인덱스는 1부터 시작(계산을 용이하게 하기 위함)하며, 자식 노드로 레벨이 내려갈 수록 인덱스는 2배씩 커짐 (왼쪽 노드 기준)

: 우선순위큐, 다익스트라 알고리즘, 중앙값의 근사값 찾는 문제에 활용

 

• 삽입 연산 - Up Heap 사용

1. 요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입한다.
2. 부모 값과 비교해 값이 더 작은 경우 위치를 바꾼다.
3. 가장 작은 값이 루트가 될 때까지 계속해서 2를 반복한다.

# 이진 힙 구현
class BinaryHeap(object): # 인덱스 0 비워둠
    def __init__(self):
        self.items = [None]
        
    def __len__(self): # 마지막 요소의 인덱스 가져오기 위함
        return len(self.items) - 1
        
# 삽입 -> heapq.heappush()
def _percolate_up(self):
    i = len(self) # index
    parent = i // 2 # 레벨 별 인덱스가 2배가 되므로
    while parent > 0:
        if self.items[i] < self.items[parent]:
            self.items[parent], self.items[i] = self.items[i], self.items[parent]
        
        i = parent
        parent = i // 2 # 위의 단계 반복

def insert(self, k):
    self.items.append(k) # 배열의 맨 마지막에 할당
    self._percolate_up() # 부모노드와 자리 바꾸기

 

• 추출 연산 - Heap Down 사용

Heap 추출시에는 루트 노드부터 제거한다. 이후, 아래 노드들 중 가장 작은 노드 (최소힙이므로)를 찾을 때까지 재귀구조로 노드의 위치를 swap하여 힙의 형태를 유지하도록 만든다. 

# 최소 힙 알고리즘 구현
def _percolate_down(self, idx):
    left = idx * 2
    right = idx * 2 + 1
    smallest = idx
    
    if left <= len(self) and self.items[left] < self.items[smallest]:
        smallest = left
    
    if right <= len(self) and self.items[right] < self.items[smallest]:
        smallest = right
        
    if smallest != idx:
        self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx] # swap
        self._percolate_down(smallest)
        
# 추출 -> heapq.heappop()
def extract(self):
    extracted = self.items[1] # 루트 값 추출
    self.items[1] = self.items[len(self)]
    self.items.pop()
    self._percolate_down(1)
    return extracted