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

힙(Heap)이란?

힙은 완전 이진트리의 일종으로, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조이다.

최댓값 및 최솟값에서 알 수 있겠지만, 힙의 종류로는 최대 힙과 최소 힙이 있다.

 

• 최대 힙

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

루트값이 가장 큰 값(최댓값)을 갖는다.

 

• 최소 힙

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

루트값이 가장 작은 값(최솟값)을 갖는다.

 

우선순위 큐란?

큐(Queue)라고 되어 있어서 일반적인 큐와 동일하게 FIFO(First-In-First-Out)방식의 자료구조를 생각할 수도 있겠지만, 우선순위 큐는 큐와는 전혀 다른 자료구조이다.

우선순위라는 말 그대로, 우선순위 큐에 있는 요소들간에 우선순위를 매겨서 우선순위가 가장 높은 요소부터 선출하는 방식을 우선순위 큐라고 한다.(반대로 우선순위가 낮으면 마지막에 선출된다.)

 

일반적으로 힙을 이용하여 구현할 수 있다.