Binary Heap(이진 힙)

Binary Heap(이진 힙)은 Complete Binary Tree 형식의 자료구조입니다.

Complete Binary Tree는 배열에 기반하고 있기 때문에 random access가 가능합니다.

Complete Binary Tree에 대한 설명은 아래 게시물을 참고해주세요.

http://dvpzeekke.tistory.com/m/45

BST(Binary Search Tree, 이진 탐색 트리)

 

Heap에는 Max Heap, Min Heap 두 종류가 있습니다.

Max Heap은 각 노드의 값이 children의 값보다 크거나 작은 Complete Binary Tree입니다.

Min Heap은 각 노드의 값이 children의 값보다 작거나 같은 Complete Binary Tree입니다.

 

Max Heap에서는 root 노드에 있는 값이 가장 크므로, 최댓값을 찾는데에 소요되는 time complextity가 O(1)입니다.

Min Heap에서는 root 노드에 있는 값이 가장 작으므로 최솟값을 찾는데에 소요되는 time complexity가 O(1)입니다.

 

하지만 만약, Max Heap에서 최댓값을 제거하는 과정을 거친다면 O(log n)의 time complexity가 소요됩니다.

Max Heap에서 root 노드를 제거하면, 다시 Max Heap 구조를 유지하기 위한 과정이 필요하기 때문입니다.

먼저 맨 마지막 노드를 root 노드로 대체하고, heapify 과정을 거쳐서 구조를 유지합니다.

마찬가지로, Min Heap에서 최솟값을 제거하는 과정을 거친다면 O(log n)의 time complexity가 O(1)입니다.