힙, 우선순위 큐

📌 힙(Heap)

완전 이진 트리를 기초로 하며, 최소 혹은 최대값을 빠르게 찾아내도록 만들어진 자료구조

우선순위 큐 (Priority Queue)와 같이 최대, 최소값을 효율적으로 찾기 위한 자료구조, 알고리즘 구현에 활용한다.

📌 종류

최대 힙 (Max Heap) : 각 노드의 값이 자식 노드가 가진 값보다 항상 크거나 같은 힙. Root의 값은 항상 최댓값이다.

최소 힙 (Min Heap) : 각 노드의 값이 자식 노드가 가진 값보다 항상 작거나 같은 힙. Root의 값은 항상 최솟값이다.

📌 구현(최대힙 기준)

부모 노드의 인덱스를 i라고 하면

왼쪽 자식 노드 : 2 x i
오른쪽 자식 노드 : (2 x i)+ 1
부모 노드 : 자식노드 인덱스 / 2

• 삽입

1. 가장 마지막 노드에 값을 삽입
2. 부모노드와 비교

부모노드보다 크면 교환
부모노드보다 작으면 그만

fun insertHeap(x: Int) {
    maxHeap.add(lastIndex, x) 
        
    var i = maxHeap.heapSize
    while (i > 1) {
        if (maxHeap.get(i / 2) < maxHeap.get(i)) {
            swap(i / 2, i)
        } else {
            break
        }
        i /= 2
    }
}

• 삭제

1. 루트 노드 삭제 (루트 노드가 가장 큰 값이므로)
2. 마지막 노드를 루트노드로 가져옴
3. 최대힙 재구성

두 개의 자식노드 중 더 큰 값과 교환
두 개의 자식노드보다 크면 동작 종료

fun deleteHeap(): Int {
   val item: Int = maxHeap.get(1) 
   maxHeap.get(1) = maxHeap.get(heapSize)
   maxHeap.remove(heapSize)
   
   var i = 1
   while (i * 2 <= heapSize) {
       i = if (maxHeap.get(i) > maxHeap.get(i * 2) && maxHeap.get(i) > maxHeap.get(i * 2 + 1)) {
                break
       } else if (maxHeap.get(i * 2) > maxHeap.get(i * 2 + 1)) {
                swap(i, i * 2)
                i * 2
       } else {
                swap(i, i * 2 + 1)
                i * 2 + 1
              }
       }
   return item
}

시간 복잡도 :

• 최소, 최대 힙에서 각각 최소, 최댓값을 구할 때는 O(1)
• 삽입, 삭제 시 최악의 경우 root부터 leaf까지 비교 후 삽입하므로 O(log n). 완전 이진 트리이므로 skew tree의 구조를 가지지 않음.

📌 우선순위 큐(PriorityQueue)

우선순위 큐(Priority Queue)는 큐(Queue)처럼 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

import java.util.*

// min heap
val pq = PriorityQueue<Int>()
pq.add(3)
pq.add(4)
pq.add(5)
pq.add(2)
pq.add(1)
println(pq)
// [1, 2, 5, 4, 3]

// max heap
val pq = PriorityQueue<Int>(Collections.reverseOrder())
pq.add(3)
pq.add(4)
pq.add(5)
pq.add(2)
pq.add(1)
println(pq)
// [5, 3, 4, 2, 1]