Heap

Heap은 Recursively하게 다음과 같은 속성을 가지고 있다.

- Max Heap 일 때 : C 노드가 있을 때, P가 C의 부모 노드라면 P의 값은 C보다 같거나 커야 한다. (C <= P) 

- Min Heap 일 때 : C 노드가 있을 때, P가 C의 부모 노드라면 P의 값은 C보다 같거나 작아야 한다. (C >= P)

(여기서 P는 부모가 없는 노드로 루트 노드라 일컫는다.)

이렇듯 Heap은 위와 같은 속성을 지닌 "트리" 기반의 자료 구조이다. (일반적으로 Heap의 트리는 완전한 바이너리 트리(Binary Tree)를 사용한다.)

또한 Heap은 우선 순위 큐(Priority Queue)로도 볼 수 있는데 우선 순위 큐 방식이 Heap과 동일하게 가장 높은 값을 루트 노드에 놓거나 가장 작은 값을 루트 노드에 놓기 떄문이다.

다만 Heap이 바이너리 트리를 사용하기도 하고 무조건 루트를 사용하므로 정렬이 되어있다고 할 수는 없다. (그래서 Heap Sorting 알고리즘이 있는 것이기도 하다.)

그럼 실제 Heap 코드를 살펴보기 전에 다시 한번 Heap 속성을 확인해보면 다음과 같다.

1) 완전 트리 (마지막 Level을 제외하고 모든 Level에 노드가 존재해야 한다.)

2) Min Heap 일 때는 최소값이 루트 노드에 Max Heap 일 때는 최대 값이 루트 노드에 존재 (모든 노드에 Recursively하게 적용)

위의 그림이 Min Heap 일 때의 완전한 트리이다. 또한 구조체 방식이 아닌 배열을 통해 트리의 각 인덱스에 Mapping이 어떻게 되고 있는지 확인 할 수 있다.

그런데 Mapping은 Heap 특성은 아니라 트리의 특성으로 접근 할 수 있는 방식인데 각 노드 계산 방식은 아래와 같다.

- 루트 노드 : Index 0

- 부모 노드 : Array[(i-1)/2]

- 왼쪽 자식 노드 : Array[(2*i + 1]

- 오른쪽 자식 노드 : Array[2*i + 2] 

이를 바탕으로 Min Heap를 구성하는 요소요소를 코드로 살펴보자. (기본을 위해 C++ 코드를 먼저 살펴보려고 한다.)

void MinHeap::insertKey(int k) {     if (heap_size == capacity)     {         cout << "\nOverflow: Could not insertKey\n";         return;     }        // First insert the new key at the end     heap_size++;     int i = heap_size - 1;     harr[i] = k;        // Fix the min heap property if it is violated     while (i != 0 && harr[parent(i)] > harr[i])     {        swap(&harr[i], &harr[parent(i)]);        i = parent(i);     } }

먼저 Insert를 살펴보면, 크게 2가지 작업으로 나뉜다.

1) Heap의 가장 마지막에 값이 k를 넣는다. (배열을 통해 Heap을 생성하기 때문에)

2) 마지막 Heap의 Index의 부모 노드와 비교하여 k 값이 작으면 부모 노드와 swap 한다. 그리고 계속해서 k 값이 부모 노드와 비교하고 swap 한다.

당연히 Heap Sorting이 아니기 때문에 자식 노드간에 비교 없이 무조건 부모 노드만 찾아간다.

void MinHeap::deleteKey(int i) {     decreaseKey(i, INT_MIN);     extractMin(); } void MinHeap::decreaseKey(int i, int new_val) {     harr[i] = new_val;     while (i != 0 && harr[parent(i)] > harr[i])     {        swap(&harr[i], &harr[parent(i)]);        i = parent(i);     } } int MinHeap::extractMin() {     if (heap_size <= 0)         return INT_MAX;     if (heap_size == 1)     {         heap_size--;         return harr[0];     }        // Store the minimum value, and remove it from heap     int root = harr[0];     harr[0] = harr[heap_size-1];     heap_size--;     MinHeapify(0);        return root; }   void MinHeap::MinHeapify(int i) {     int l = left(i);     int r = right(i);     int smallest = i;     if (l < heap_size && harr[l] < harr[i])         smallest = l;     if (r < heap_size && harr[r] < harr[smallest])         smallest = r;     if (smallest != i)     {         swap(&harr[i], &harr[smallest]);         MinHeapify(smallest);     } }

다음으로 delete는 insert 보다 조금 복잡하다. (당연히 추가보다 삭제가 어렵기 때문에)

1) 지우려는 인덱스의 값을 INT_MIN (큰 음수 값)으로 변경한다.

2) 부모 노드와 비교하여 부모 노드가 클 경우 swap한다. 그리고 계속해서 INT_MIN 값이 클 때 까지 한다. (보통 루트 노드가 되었을 때 종료된다.)

3) 가장 마지막에 있는 노드 값을 루트 노드에 넣는다. (마지막 노드는 삭제)

4) 루트 노드에 있는 값을 자식 노드 왼쪽, 오른쪽 중 더 작은 노드를 찾아 swap한다. 그리고 계속해서 트리 Level을 내려가며 swap 한다.

이렇듯, Heap은 루트 노드의 값이 명확하기 때문에 부모 노드와 자식 노드간의 swap을 통해 원하는 값을 얻을 수 있다.

Reference

- https://www.geeksforgeeks.org/heap-data-structure/

- https://www.geeksforgeeks.org/binary-heap/