자료구조 - 힙(Heap)이란?

힙(Heap)

 

힙(Heap)은 우선 순위 큐를 구현하기 위해 사용되는 자료구조이다. 기반은 트리 형태이며 삽입, 삭제 모두 O(logN)의 시간복잡도를 가진다.

 

---

 

우선순위 큐(Priority Queue)

 

우선순위 큐는 큐의 구조에서 요소별 가중치를 두어 우선순위를 정하여 pop()을 실행하는 자료구조이다. 예전에 queue를 정리해놓은 포스팅에서 언급한 적이 있듯이 어떤 작업을 수행할 때 단순 FIFO 방식을 따르는 것은 때론 비효율적으로 동작할 수 있다. 예를 들어, 운영체제의 프로세스 작업 스케쥴링에서 여러 방법들 중 우선순위 큐를 사용하여 스케쥴링 하는 방법이 있다.

 

 

---

힙의 특징

 

1. 위에서 언급했듯 힙은 트리의 형태를 취하고 있으며 많은 트리의 종류들 중에서도 완전 이진 트리의 구조를 가진다..힙은 결국 최댓값이나 최솟값을 빠르게 찾기 위해 고안된 자료구조이다. 따라서 max, min 값을 O(1)의 시간복잡도로 찾을 수 있어야 한다.
2. 힙은 BST와 다르게 중복된 값을 허용한다.
3. 힙의 종류로는 최대힙과 최소힙이 존재한다.
   • 최대힙 : 각 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리를 말한다.
   • 최소힙 : 각 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리를 말한다.
4. 최대힙에서는 Root Node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다. 그러나 최댓값을 pop() 할 경우 heap의 구조를 유지하기 위해 logN의 연산이 수행된다. 최소힙에서도 마찬가지이다.
5. Complete Binary Tree이기 때문에 배열을 이용해 관리할 수 있으며, 인덱스를 통한 Random Access가 가능하다.
   • Index 번호는 노드 개수가 n개일 때, i번째 노드에 대하여 왼쪽 자식은 ix2, 오른쪽 자식은 ix2+1가 된다.

 

힙의 구조

 다음은 최대힙과 최소힙의 구조이다. 최대힙은 부모 노드가 자식 노드보다 항상 크거나 같아야 하고, 최소힙은 그 반대이다.

 

 

 

---

힙의 구현

 

힙은 배열로 구현할 수 있다.
index값은

• i번째 노드의 왼쪽 자식 : 2i
• i번째 노드의 오른쪽 자식 : 2i+1

이다.

 

 

Python의 경우

import heapq

를 통해 heappop()과 heappush()를 사용할 수 있다.