[자료구조]힙(Heap)

본문에서는 최소힙 (min heap) 기준으로 설명하도록 하겠습니다.

힙(Heap) 이란?

우선순위 큐를 구현하는데 주로 사용되는 자료구조로써 완전 이진트리로 구성되며 반정렬(느슨한 정렬) 상태입니다.

반정렬(느슨한 정렬)?

모든 노드가 자식 노드의 키 값보다는 크기가 작거나 같으며 부모 노드의 키 값보다는 크기가 큽니다.

크기가 가장 작은 값은 루트 노드에 있어야 합니다.

 

또한 힙에서는 중복된 값을 허용합니다.

 

힙(Heap)의 종류

• 최소 힙(Min Heap) - 부모 노드 key 값 <= 자식 노드 key 값
• 최대 힙(Max Heap) - 부모 노드 key 값 >= 자식 노드 key 값

힙(Heap)의 구현

heap은 완전 트리이기 때문에 배열로 구현할 수 있습니다.

위와 같은 힙이 있다고 할때 아래와 같은 배열로 나타낼 수 있습니다.

 이 때 인덱스를 구성하는 성질이 있습니다.

• 루트 노드의 인덱스는 1로 한다.
• 자신의 index를 i라 할 때
  왼쪽 자식의 index = 2 * i (2 * i <= n)
  오른쪽 자식의 index = 2 * i + 1 (2 * i + 1 <= n)
• 부모의 index = floor(i / 2) (i >= 2)

 

힙(Heap) 구조화- heapify

삽입과 삭제로 깨진 heap을 재구조화하는 heapify의 과정은 \(O(logN)\) 의 시간복잡도를 가지고 있습니다.

 

삽입(Inserttion) 과정

1. 힙의 가장 마지막 노드에 새로운 노드를 삽입한다.
2. 새로운 노드를 부모 노드들과 교환하며 힙의 성질을 만족시킨다.

삭제(Delete) 과정

1. 루트 노드를 삭제한다.
2. 가장 마지막 노드를 루트 노드 자리로 이동한다.
3. 루트 노드로 옮긴 노드와 자식노드를 비교하며 힙 구조를 완성시킨다. (→Percolating-down)
   단, 자식 노드 둘 다 부모 노드보다 크기가 작은 경우 자식 노드 중 더 작은 노드 쪽으로 이동한다.

 

힙(Heap) 만들기 - BuildHeap

힙 구조가 아닌 배열을 힙으로 만드는 과정입니다. 

N개의 자료에 대하여 Heapify 과정 \(O(logN)\)을 거치기 때문에 시간 복잡도는 \(O(NlogN)\)이 됩니다.

1. 가장 낮은 위치에 있는 자식이 있는 노드 부터 시작gkqslek.
2. 루트노드방향으로 이동하며 자식노드를 비교하며 힙 구조를 완성시킵니다. ( → percolating-down)

 

참고 자료

• Fundamentals of Data Structures in C (2nd Edition)
• emplam27.log