[Data Structure] Heaps - 1 | Max-heap (최대 힙) and Min-heap (최소 힙)

Heaps Concept

때때로 프로그램들은 변화하는 데이터 셋에서 최대/최소값의 아이템을 빠르게 접근하고 제거할 수 있는 능력이 필요합니다. 

이럴 때 힙 자료 구조는 아주 유용합니다. 

---

 

Max-Heap

Maintaining jobs in fully-sorted order requires more operations than necessary, since only the maximum item is needed. A max-heap is a complete binary tree that maintains the simple property that a node's key is greater than equal to the node's children's keys. (Max heap, 최대힙은 어떤 트리 구조여도 가능하지만, 일반적으로는 이진 트리를 사용합니다.)

우선 쉽게 이해하자면 정렬될 필요가 없는 (이진) 트리 구조이고, 부모 노드의 값이 자식 노드의 값보다 커야합니다. 이런 이유로 가장 큰 값을 가지는 노드가 root node일 수 밖에 없습니다.

 

이해를 위해 다음 이진 트리를 살펴봅시다:

이 이진 트리가 최대 힙이 될 수 없는 이유는 60 노드가 55의 자식 노드인 것 때문이겠죠? 

주의해야 할 점은 규칙은 단순히 부모 노드가 자식 노드보다 커야한다 뿐입니다. 

54 노드가 44 노드보다 값이 크지만 레벨이 하나 더 높다고 해서 문제가 되지 않습니다. 54가 44의 자식이 아니니까요. 

 

---

Max-heap Insert and Remove Operations

An insert into a max-heap starts by inserting the node in the tree's last level, and then swapping the node with its parent until no max-heap property violation occurs. Inserts fill a level (left to right) before adding another level, so the tree's height is always the minimum possible. The upward movement of a node in a max-heap is called percolating. 

A remove from a max-heap is always a removal of the root, and is done by replacing the root with the last level's last node, and swapping that node with its greatest child until no max-heap property violation occurs. Because upon completion that node will occupy another node's location (which was swapped upwards), the tree height remains the minimum possible. 

* Given N nodes, the height of a max-heap is ⌊log₂N⌋

* Thus, given a max-heap with N nodes, the worst-case complexity of an insert is O(logN)

* For the same reason, the worst-case complexity of a removal is O(logN)

 

---

Min-Heap

A min-heap is similar to a max-heap, but a node's key is less tha nor equal to its children's keys. 

단순히 max-heap의 규칙이 거꾸로 적용되어서 root node가 최소값인 트리를 생각하시면 됩니다. 

 

Min-heap이 자주 사용되는 분야 중 하나는 customer services 입니다. 많은 customer services queue 시스템은 먼저 대기중인 고객 또는 긴급하거나 우선순위가 있는 고객에게 더욱 낮은 값을 부여합니다. 이후 고객 응대가 가능한 직원이 생겼을 때, 가장 낮은 값 (root node)을 가지는 대기 손님부터 우선적으로 상담을 시작하는 식입니다.