개념

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

• max heap : 부모노드 > 자식노드
  • 큰 것부터 뽑힘
• min heap : 부모노드 < 자식노드
  • 작은 것 부터 뽑힘

Python

queue모듈의 PriorityQueue를 사용하거나 heapq 모듈을 사용할 수 있다.

Python으로 Heap사용하는 법

구현방법은 C에서 다룬다.

C (직접 구현)

int타입의 heap

배열로 heap을 구현한다.

배열의 인덱스가 다음의 규칙을 따르게 한다.

• 0번째 index는 사용하지 않는다. (MAX로 설정)
• 2i번째의 자식 노드를 i, i+1째로 둔다.

Heap Sorting을 구현하면서 Heap도 같이 구현한다.

• insert
• extract