Heap

• Array로 구현 가능한 Complete Binary Tree의 일종. 모든 부모 노드가 자식 노드보다 큰 경우, Max Heap. 그 반대의 경우, Min Heap.

데이터 처리

• 삽입: 완전이진트리의 규칙을 깨지 않도록, 언제나 최하단 최우측에 삽입됨.
• Root Node 제거: 완전이진트리의 규칙을 깨지 않도록, 최하단 최우측 노드를 루트노드 위치에 옮긴 뒤, 정렬 수행.

파이썬에서는 기본적으로 heapq를 쓸 경우 min-heap이다. pop연산에서 우선 방출되는것은 인덱스 0에 있는 것이며, 이것은 루트노드가 pop되는 것과 개념적으로 동일하다. 즉, min-heap에서 정렬은 <를 기준으로 오름차순으로 정렬된다.