[Algorithm] 힙

 

 

* Python을 기준으로 합니다

---

힙 (Heap)

- 개념

• 힙 : 특정 조건을 만족하면서 항상 완전 이진 트리 형태를 가지는 자료구조
  • 힙의 조건
    1. 최대힙 : parent 노드가 항상 child 노드 보다 크거나 같다는 조건을 만족하는 힙
    2. 최소힙 : parent 노드가 항상 child 노드 보다 작거나 같다는 조건을 만족하는 힙
       - 해당 힙 구조를 기반으로 최대/최소값 탐색을 $O(1)$ 내에 처리 가능 
  • 이때 힙은 단순히 위의 조건들만을 만족할 뿐, 정렬된 상태는 아님
    - 구조적으로는 이진 탐색 트리와 유사하기 때문에 대부분의 연산은 $O(\log n)$ 내에 끝남
    - BUT, 힙은 상/하 관계를 보장하고 이진 탐색 트리는 좌/우 관계를 보장한다는 차이가 있음
  • 사용 예시 : 우선순위 큐, 힙 정렬, 다익스트라, 최소 신장 트리 (Prim 알고리즘)

- 구현

1. heapq 라이브러리를 통한 힙의 구현

• `heapq` 라이브러리는 최소힙 구조를 지원함, 최대힙의 경우 음수를 취함으로써 구현 가능
  • `heapify(list)` : 주어진 배열을 최소힙으로 생성함
  • `heappush(heap, data)` : 힙에 데이터 추가
  • `heappop(heap)` : 힙에서 최소값을 pop
  • `heappushpop(heap, data)` : push, pop을 한 번에 수행
  • `nlargest(n, heap)` : $n$번째 최대값 추출 (가장 큰 값부터 $n$번째까지 배열 형태로 반환됨)
  • `nsmallest(n, heap)` : $n$번째 최소값 추출 (가장 작은 값부터 $n$번째 까지 배열 형태로 반환됨)

import heapq

heap = [54, 31, 90, 12, 46, 87, 10, 9, 123, 67]

#최소힙 생성
heapq.heapify(heap)
print(heap) #[9, 12, 10, 31, 46, 87, 90, 54, 123, 67]

#힙 push
heapq.heappush(heap, 7)
print(heap) #[7, 9, 10, 31, 12, 87, 90, 54, 123, 67, 46]

#힙 pushpop
heapq.heappushpop(heap, 100)
print(heap) #[9, 12, 10, 31, 46, 87, 90, 54, 123, 67, 100]

#n번째 최대, 최소값 찾기
print(heapq.nsmallest(4, heap)) #[9, 10, 12, 31]
print(heapq.nlargest(4, heap)) #[123, 100, 90, 87]

#힙 pop
for i in range(len(heap)):
  print(heapq.heappop(heap), end=' ') #9 10 12 31 46 54 67 87 90 100 123

2. 배열을 통한 힙의 구현

• 힙은 기본적으로 배열을 사용하여 구현함

class MinHeap:
    def __init__(self):
        self.arr = [None]

• 힙의 삽입 연산 (최소힙 기준) : 삽입 시에는 up-heap 연산이 수행됨 
  
  1. 삽입할 값을 가장 하위 level의 가장 왼쪽 노드로 삽입
  2. Parent의 값과 비교하여 더 작으면 위치를 변경
  3. 이후 위 과정을 반복 (가장 작은 값일 경우 root까지)

def _swap(self, x, y): # node 위치 변경
  self.arr[x], self.arr[y] = self.arr[y], self.arr[x]

# 삽입 연산
def insert(self, val):
  self.arr.append(val)
  self.up_heap() #up-heap
  
#up-heap 연산
def up_heap(self):
  idx = len(self.arr) - 1
  parent = idx // 2

  while parent > 0:
    if self.arr[idx] < self.arr[parent]: #현재 값이 parent 보다 작으면
      self._swap(parent, idx) #parent, child 위치 변경
      idx = parent
      parent = idx // 2
    else:
      break

• 힙의 추출 연산 (최소힙 기준) : root 노드를 추출하고, down-heap 연산으로 힙을 재구축함
  1. root 노드를 추출하여 최소값을 얻음
  2. 빈 root 노드에는 힙의 가장 마지막 노드 값을 위치시킴
  3. Child 노드와 비교해서 값이 더 크면 위치 변경
  4. 2~3번 과정을 반복하여 힙을 재구축

#추출 연산
def extract(self):
  if len(self.arr)-1 == 0:
    return 0
  
  val = self.arr[1] #root의 데이터 추출
  self._swap(1, len(self.arr)-1) #힙의 가장 마지막 노드를 가져옴
  self.arr.pop() #root 제거
  self.down_heap(1) #down-heap
  
  return val

#down-heap 연산
def down_heap(self, idx):
  left = 2*idx
  right = 2*idx + 1
  _min = idx
  
  if left <= len(self.arr)-1 and self.arr[left] < self.arr[_min]: #left child 보다 작으면
    _min = left #left child의 index를 가져옴
    
  if right <= len(self.arr)-1 and self.arr[right] < self.arr[_min]: #right child 보다 작으면
    _min = right #right child의 index를 가져옴
    
  if _min != idx: #index가 변경되었다면
    self._swap(idx, _min) #해당 index로 위치를 변경하고,
    self.down_heap(_min) #down-heap 반복

• 결과 확인

heap = [54, 31, 90, 12, 46, 87, 10, 9, 123, 67]
mhp = MinHeap()

for i in range(len(heap)):
  mhp.insert(heap[i])
    
for i in range(len(heap)):
  print(mhp.extract(), end=' ') #9 10 12 31 46 54 67 87 90 123