[자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

우선순위 큐 전에 큐에 대해 알아보고 왔다.

큐는 처음 들어온 값이 처음으로 나가는 FIFO(First Input First Output) 형식의 자료구조였다.

그렇다면 우선순위 큐도 위와 같을까?

 

우선순위 큐는 이름에서 알 수 있듯이, 데이터가 들어온 순서가 아닌 우선순위가 높은 데이터부터 나가게 되는 자료구조이다.

즉, 가장 먼저 들어왔다고 해서 가장 먼저 나가는 형식이 아니다.

우선순위 큐는 힙(Heap)을 이용하여 구현된다.

 

따라서 힙에 대해 먼저 알아보려고 한다.

힙(Heap)

힙은 우선순위 큐를 위해 만들어진 자료구조이다.

완전 이진 트리 형태로 이루어져 있으며, 반정렬 상태(느슨한 정렬 상태)를 유지하며 부모노드와 서브트리간 대소 관계가 성립된다.

간단히, 부모 노드의 키 값이 자식 노드의 값보다 큰 혹은 작은(정렬된 기준에 따라 다르다.) 이진 트리를 의미한다.

힙의 종류

힙은 두 가지의 종류로 나눌 수 있다.

1. 최대 힙(Max Heap)

• 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리 형태이다.

2. 최소 힙(Min Heap)

• 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리 형태이다.

힙의 구현

package datastructure

// 최대힙 구현
class Heap {
    private var heap = mutableListOf<Int>()

    fun push(data: Int) {
        heap.add(data)

        var idx = heap.size - 1
        while(idx > 0 && heap[(idx-1) / 2] < heap[idx]) {
            swap((idx - 1) / 2, idx)
            idx = (idx - 1) / 2
        }
    }

    private fun swap(from: Int, to: Int) {
        val temp = heap[from]
        heap[from] = heap[to]
        heap[to] = temp
    }

    fun pop(): Int {
        if(heap.isEmpty()) return -1

        val data = heap[0]
        heap[0] = heap[heap.size - 1]
        heap.removeAt(heap.size - 1)

        var cur = 0
        while(true) {
            val left = cur * 2 + 1
            val right = cur * 2 + 2

            if(left >= heap.size) break

            var next = cur

            if(heap[next] < heap[left]) next = left
            if(right < heap.size && heap[next] < heap[right]) next = right

            if(next == cur) break

            swap(cur, next)
            cur = next
        }

        return data
    }

    fun print() {
        println(heap)
    }
}

fun main() {
    val heap = Heap()
    heap.push(2)
    heap.push(3)
    heap.push(5)
    println(heap.pop())
    heap.print()
}