[파이썬] 힙(Heap) 직접 구현하기

  힙(Heap)은 최대값이나 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 이다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리를 말한다. 최대값을 구하기 위한 최대 힙(Max Heap)과 최소값을 구하기 위한 최소 힙(Min Heap) 으로 분류되고, 최대 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같고 최소 힙은 그 반대이다.



 

 

  힙은 배열을 이용해 구현할 수 있고, 편의를 위해 0번 인덱스 대신 1번 인덱스를 루트 노드로 지정한다.

 

• 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
• 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

 

 

 

 

  이진 탐색 트리(Binary Search Tree)의 경우, 작은 값은 왼쪽 자식 노드로, 큰 값은 오른쪽 자식 노드로 보내는 조건이 있다. 따라서 이진 탐색 트리의 가장 왼쪽 자식이 최소값이고 가장 오른쪽 자식이 최대값이다. 반면에 힙의 자식 노드는 오른쪽이 클 수도 있고 왼쪽이 클 수도 있다. 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값을 찾기 위한 구조로 이해하면 된다.

 

힙과 이진 탐색 트리 비교

  < 힙 구현하기 >

* 시간 복잡도

  트리의 높이(Depth)를 ℎ 라고 한다면, 힙의 시간 복잡도는 O(ℎ) 이다. n 개의 노드를 가지는 힙에 데이터 삽입 또는 삭제시 최악의 경우 ℎ=𝑙𝑜𝑔𝑛 에 가까우므로 O(𝑙𝑜𝑔𝑛) 이라고 말할 수 있다.