[자료구조] priority queue

priority queue

Queue 자료구조는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장하는 형식이다. 이와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

Queue의 operation 시간복잡도는 enquque O(1), dequeueO(1)이고,
priority queue는 pushO(logn), popO(logn)으로, 이는 이진완전트리를 활용한 Heap 자료구조의 push와 pop과 동일하다.

Heap

Heap은 완전이진트리 구조이며, 우선순위큐의 구현과 일치한다.
이러한 Heap이 되기 위한 조건은 아래와 같다.

Max Heap

root node에 저장된 값이 가장 큰 값이며, 각 node에 저장된 값은 child node들에 저장된 값보다 크거나 같다.

Min Heap

root node에 저장된 값이 가장 작은 값이며, 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다.

Heap 구현

트리는 보통 Linked List로 구현한다. 하지만 Heap은 tree임에도 불구하고, array를 기반으로 구현해야 한다. 새로운 node를 힙의 마지막 위치에 추가해야 하는데, 이때 array기반으로 구현해야 이 과정이 수월하기 때문이다.

구현의 편의를 위해 array의 0번째 index는 사용하지 않고, 완전이진트리의 특성을 활용하여 array의 index만으로 부모 자식간의 관계를 정의한다.

• n번 째 node의 왼쪽 자식 노드 = 2n
• n번 째 node의 오른쪽 자식 노드 = 2n + 1
• n번 째 node의 부모 노드 = n/2

Heap pust - O(logn)

heap tree의 높이는 logn이다.
push()했을 때, swap하는 과정이 최대 logn번 반복되기 때문에 시간복잡도는 O(logn)이다.

Heap pop - O(logn)

pop()했을 때, swap하는 과정이 최대 logn번 반복되기 때문에 시간복잡도는 O(logn)이다.