[자료구조] Heap (python heapq)

우선순위 큐에 대한 설명

[파이썬 알고리즘] 10장 우선순위 큐 (priority queue) with Heap

 

---

python.flowdas.com/library/heapq.html#heapq.heappop

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

 

• Heap은 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리이다.
• 파이썬에서의 heapq는 min heap(최소힙)이다.
  • 작을수록 우선순위가 높게 평가하는 것
• 모든 K에 대해 다음을 만족한다.
  • heap[k] <= heap[2*k+1]
  • heap[k] <= heap[2*k+2]
• python에서 요소는 0부터 시작한다.
  • python에서는 힙에서 가장 작은 요소를 heap[0]에 둔다는 점이다.

---

• heapq.heappush(heap, item)
  • item을 heap으로 push
• heapq.heappop(heap)
  • heap에서 가장 작은 항목을 pop
  • heap이 비어있다면 IndexError 발생
• heapq.heappushpop(heap, item)
  • 힙에 item을 push한 다음, heap에서 가장 작은 항목을 pop
  • heapq.heappush와 heapq.heappop을 이어서 호출하는 것과 동일한 결과이지만, 더 효율적으로 실행
• heapq.heapify(x)
  • 리스트 x를 heap으로 변환한다.
• heapq.heapreplace(heap, item)
  • heap에서 가장 작은 항목을 pop하고 반환  & 새로운 item 푸시
  • heapq.pop와 heapq.push를 이어서 호출하는 것과 동일한 결과이지만, 더 효율적으로 실행
• heapq.merge(*iterables, key=None, reverse=True)
  • 여러 정렬된 입력을 단일 정렬된 출력으로 병합
• heapq.nlargest(n, iterable, key=None)
  • n개의 가장 큰 요소로 구성된 리스트 반환
• heapq.nsmallest(n, iterable, key=None)
  • n개의 가장 작은 요소로 구성된 리스트 반환