PriorityQueue & Heap

PriorityQueue

---

 우리는 이전에 Queue의 구조에 대하여 학습한적이 있다. Queue는 First In First Out 구조로 먼저 집어넣은 데이터가 먼저 나오는 구조를 가지고 있다. 하지만 PriorityQueue는 이름에서 알 수 있듯이 Queue의 구조에서 데이터의 우선순위에 따라서 우선순위가 높은 데이터가 먼저 나오는 구조를 가지고 있다.

 위의 구조는 PriorityQueue의 구조이다. 데이터를 무작위로 Enqueue 했을때 그 순서와 상관없이 우선순위가 높은 데이터가 가장 왼쪽에 위치하는 것을 알 수 있다.

 

 구현

 PriorityQueue의 구현은 Array, LinkedList, Heap으로 가능하다. 다만 Array와 LinkedList는 매번 가장 높은 우선순위의 데이터를 가장 왼쪽으로 보내야 하는 PriorityQueue의 방식과는 맞지가 않는다. 이전에 ArrayList와 LinkedList를 공부할때 알게 되었던 단점들이 그 원인이다. Array는 데이터를 중간에 삽입할 때 그 뒤의 데이터들을 그만큼 뒤로 밀어야 하고 LinkedList는 삽입할 위치를 찾는데 많은 시간이 걸리기 때문에 PriorityQueue에는 적합하지 않다. 그래서 우리는 주로 Heap을 이용해서 PriorityQueue를 구현한다.

 

Heap

---

Heap은 Binary Heap 즉 이진 Heap이라고도 하며, Complete Binary Tree(완전 이진 트리)를 기본으로 한 자료구조이다.  

1. Heap은 Complete Binary Tree이다.
2. 부모 노드에 저장된 우선순위는 자식 노드에 저장된 우선순위 보다 크거나 같다. 다만 형제 노드간의 대소관계는 정해지지 않는다.

종류

Heap에는 루트 노드로 올라갈수록 저장된 값이 커지는 Max Heap(최대 힙), 루트 노드로 올라갈수록 값이 작아지는 구조를 가지는 Min Heap(최소 힙)이 존재한다. 

                                      Max Heap                                                                              Min Heap

 이런 Heap 구조에서 만약 데이터를 삽입하고자 한다면, 새로 들어올 데이터의 우선순위를 가장 낮거나, 가장 높을 것이라고 가정을 하고 위치가 맞을때까지 부모 노드와 바꿔가는 방식으로 삽입이 이뤄지게 된다.

 Heap은 일반적으로 Array로 표현하게 되고 개발 편의성을 위해 Array index[1] 부터 사용하게 된다. (index[0] 미사용)

 

 

PriorityQueue 구현

---

 내가 사용하는 JAVA나 Kotlin에서는 PriorityQueue 클래스가 존재하기 때문에 쉽게  PriorityQueue를 구현할 수 있다.

fun main(args : Array<String>) {
    val pq = PriorityQueue<Int>()

    pq.add(4)
    pq.addAll(listOf(1, 3, 5, 6, 6))
    pq.offer(2)
    pq.peek() // 가장 높은 우선순위 탐색
    pq.poll() // 가장 높은 우선순위 반환
}

 

Reference

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

 

Kotlin PriorityQueue(우선순위 큐)

 

[자료구조] 우선순위 큐 (Priority Queue) 개념 및 구현