[자료구조] Heap

Heap

• 힙은 자료구조의 일종으로 트리 형식을 하고 있다(Complete Binary Tree). 트리에서 가장 작은 원소를 최상위 루트에 두게 한다.
• 순서를 가진 큐나 리스트의 가장 작은 원소에 빠르게 접근해야 하는 경우에 유용하다. 우선 순위 큐(Priority Queue)를 위해 만들어진 자료구조다.
• 각 노드는 자신의 자식보다 작으므로 원소들을 순서대로 위치시키고 싶을 때 가장 유용한 방법은 아니다.
• 힙 트리에서는 중복값을 허용한다.
• 배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다. (= 노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄인다.)
• 부모노드와 자식노드를 찾기 쉽다.
  • 왼쪽 자식 노드의 인덱스 = (부모 인덱스) * 2
  • 오른쪽 자식 노드의 인덱스 = (부모 인덱스) * 2 + 1
  • 부모의 인덱스 :(자식 인덱스) / 2

힙의 시간 복잡도 [출처 : 위키] 

 

최대힙(max heap)

• 각 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리이다.
• Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complexity 이 O(1)이다. 
• complete binary tree이기 때문에 배열을 사용하여  random access 가 가능하다. (효율적으로 관리 가능!)

최소힙(min heap)

• 각 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리이다.
• Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity 가 O(1)이다.

Heapify

자료구조의 경우 삽입, 삭제, 수정이 발생한다. 이 때, heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.

 

UpHeap

• UpHeap은 힙에 새로운 원소를 삽입하고, 새로운 원소를 포함한 새로운 힙을 구성하는 과정이다.
• 새로 추가되는 원소를 가장 말단에 위치를 시키고 부모 노드와 값을 비교하여 위치를 교환하는 방식이다. 
• 삽입 연산 최악의 경우, 루트 노드까지 올라가야 하므로 트리 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. = O(logN) 

DownHeap

• 힙에서 노드를 제거하는 작업이다.
• 최대힙에서는 힙의 루트로부터 최대값을 가져오는 일을 의미한다.
  • 최대힙을 유지해야 하므로 DownHeap 과정을 거친다.
  • 가장 먼저 루트값이 비게 되므로 가장 말단에 있는 값을 루트 노드에 위치 시킨다.
  • 자식 노드와 비교를 하여 자식 노드보다 클 경우에는 그대로 유지시키고 작을 경우 자식 노드와 위치를 교환한다.
  • 이 과정을 자신이 리프 노드가 되거나 자식 노드보다 자신이 클 경우까지 반복한다.
• 삭제 연산 최악의 경우, 가장 아래 리프 노드까지 가야 하므로 트리 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. = O(logN) 

Reference

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)#%EB%B3%B5%EC%9E%A1%EB%8F%84

https://www.slideshare.net/donggyupark2/30-2-key

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#hashtable