[자료구조] 5_2. Heap

1. 정의

힙(Heap)이란 완전이진트리(Complete Binary Tree)를 기본으로 하는 Tree-based 자료 구조이다. Heap은 기본적으로 다음과 같은 조건을 만족한다.

A가 B의 부모 노드이면, A 노드의 value와 B 노드의 value 사이에는 대소관계가 성립한다.

위의 조건을 만족하는 Heap으로 Max Heap과 Min Heap을 생각해볼 수 있다. Max Heap의 경우 부모 노드가 항상 자식 노드보다 큰 경우이고, Min Heap의 경우는 그 반대로 부모 노드가 항상 자식 노드보다 작은 경우가 된다. 이러한 원리에 의해서 당연히 Max Heap의 Root는 가장 큰 값이 될 것이고, Min Heap의 Root는 가장 작은 값이 될 것이다. Heap의 규칙에 의해 Root는 항상 가장 큰 혹은 가장 작은 값이기에 최대, 최소를 찾을 때 Heap을 사용하면 유리하다.

cf) Priority Queue는 일반적으로 Heap으로 구현되어 있다.

- 성능

Binary Min Heap에서, Heap을 구축된 것을 전제로 한다.

Find Min : O(1)            // 최소값 탐색 

Delete Min : O(log n)    // 최소값 삭제

Insert : O(log n)           // 새로운 원소 삽입

2. 종류 

Heap은 기본적으로 Binary Heap이지만, 성능을 향상시킨 다양한 Heap들이 존재한다. (ex. Fibonacci Heap, Ternary Heap, ...)

- Max Heap : Root가 최대값, 부모 노드가 자식 노드보다 항상 크다.

- Min Heap : Root가 최소값, 부모 노드가 자식 모드보다 항상 작다.

- Min-Max Heap

3. 구현

1) Heap By Array

Heap의 구현은 보통 Array를 통해서 이루어진다. Tree와 마찬가지로 n번째 index의 노드가 parent라면, 2*n번째 index는 left child, 2*n+1번째 index는 right child가 된다.

ADT Heap

Data : 특별한 규칙으로 정렬되어 있는 완전 이진 트리.

Operation : 

createHeap() - 비어있는 Heap을 생성.

clear() - 생성되어있는 Heap을 삭제.

isEmpty() - Heap이 비어있는지 체크.

insert(element) - 새로운 Element를 Heap에 삽입.

remove() - isEmpty() 체크 후, 비어 있지 않은 경우 Root key 반환후 Root 삭제.

size() - Heap의 원소 개수 반환.

Max Heap

Min Heap

Tip) Max Heap을 구현했다면, Min Heap을 구현하는 데에 코드를 뜯어 고치지 말고, Max Heap에서 Insert 연산을 할 때, key에 -1을 곱하자. 이 과정을 통해서 가장 큰 key가 가장 작은 key가 된다. 따라서, Max Heap으로도 Min Heap을 구현할 수 있다. Root를 Remove할 때에도 -1을 곱해주면 원래의 값을 얻을 수도 있다.