[파이썬 | 자료구조] 8. 힙(Heap)

8. 힙(Heap)

8.1 힙의 개념

힙 역시 트리 구조를 가진 자료구조의 형태이다.

힙은 BST와 비슷하면서 다른 특징을 가지고 있다.

1. root의 값은 항상 최대/최소 이다.
2. 트리는 항상 완전이진트리이다.
3. 어떤 서브 트리 역시 힙의 특성을 그대로 가진다.

BST는 모든 원소들이 Inorder로 탐색했을시 정렬되어서 표현된다. 즉 모든 자료들이 정렬되어 있는 형태로, 탐색에 유리하다.

하지만 힙은 root의 값이 최대/최소임은 보장하지만 다른 원소들은 정렬되어 있지 않다. 따라서 BST에 비해 탐색에는 불리한 구조이다.

하지만 모든 삽입과 삭제가 맨 마지막에서 일어나므로 삽입, 삭제 연산에 있어서 장점이 있으며 부모와 자식간의 간선 정보를 수식으로 나타낼 수 있으므로, node를 사용한 연결리스트가 아닌 배열의 형태로 구현할 수 있어서 구현에 있어 장점이 있다.

일단 삽입의 경우에는 그냥 배열의 맨 마지막에 추가하면 되므로 append로 간단히 구현가능하다.

삭제의 경우에는 일단 삭제할 데이터의 index를 모두 탐색하고나서, 해당 index의 데이터와 맨 마지막의 데이터를 교환하고, 맨 마지막 데이터를 pop한다.

하지만 이렇게 하면 Heap 규칙이 깨지므로, heapify를 수행해서 max heap을 다시 구현한다.