우선순위 큐(Priority Queue)란

일단 큐는 FIFO(First In First Out) 자료구조이다. 우선순위 큐는 일반 큐와 달리 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

힙(Heap)이란

힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 구조이며 최댓값과 최솟값을 찾아내는 연산이 빠르다. 또한, 이진탐색트리(BST)와 달리 중복된 값이 허용된다.

• 완전이진트리 : 루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리

• 이진트리 : 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리

• 이진탐색트리 : 다음 조건을 만족시키는 이진트리

  • 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
  • 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
  • 같은 키 값을 갖는 노드가 없어야 한다. (중복된 값을 허용하지 않는다.)

힙의 종류

최대힙(Max Heap)

• 부모 노드의 키 값이 자식 노드보다 크거나 같다.

최소힙(Min Heap)

• 부모 노드의 키 값이 자식 노드보다 작거나 같다.

힙 구현

트리는 보통 Linked list로 구현하지만 힙은 트리임에도 불구하고 Array를 기반으로 구현해야 한다. 그 이유는 새로운 노드를 힙의 마지막 위치에 추가해야 하는데 이때 Array를 기반으로 구현해야 더 빠르기 때문이다

힙의 시간 복잡도

• push : $O(logN)$
• pop : $O(logN)$