[알고리즘] 우선순위 큐

큐(Queue)

'큐(Queue)'란 자료를 저장하고 수정하는 구조인 자료구조의 중 하나이다.

특징으로는 먼저 들어온 값이 먼저 나가는 FIFO(First In First Out)(선입선출) 구조라는 점이다.

 

 

큐(Queue)를 표현한 그림 (출처: 위키백과)

 

우선순위 큐(Priority Queue)?

우선순위 큐는 일반적인 큐와는 조금 다르다.

앞서 말했듯 원래 큐는 선입선출 구조로 되어 있어서 자료를 추출하면 가장 먼저 저장했던 데이터가 나오게 된다.

그러나 우선순위 큐는 자료들에 우선순위를 부여하여서 우선순위가 높은 데이터가 먼저 나오는 형태이다.

 

이러한 우선순위 큐를 구현할 때 사용하는 일반적이고 효율적인 구조가 힙(Heap)이다.

 

※ 우선순위 큐와 힙은 같은 것이 아니다. 우선순위 큐는 자료구조에 대한 추상적 개념이고, 힙은 구현 방식 중 하나이다.

 

힙(Heap)?

힙(Heap)은 완전이진트리 구조의 자료구조이다.

노드가 채워질때는 항상 왼쪽 자식 노드부터 채워져햐 하며, 부모노드와 자식노드 사이에 대소관계가 성립하는 반정렬상태이다.

 

※ 같은 부모 노드를 공유하는 자식 노드간의 대소관계는 상관 없다. 따라서 꼭 왼쪽 자식 노드가 더 크거나 작아야 하는 것은 아니다.

 

힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 나뉜다.

 

최대힙(Max Heap)

부모노드값이 자식노드값보다 큰 것을 말한다.

Max Heap 예시

최소힙(Min Heap)

부모노드값이 자식노드값보다 작은것을 말한다.

Min Heap 예시

 

배열로 힙 표현

힙 구조에 인덱스를 부여한 후 배열로 표현하면 다음과 같아진다.

 

이때 다음과 같은 관계가 성립한다.

• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2

 

마무리

다익스트라 알고리즘을 알아보다가 함께 알게된 내용인데, 개념 자체는 엄청 어렵진 않았다.

다만 이를 구현해보라고 하면 조금 애를 먹을 것 같다...

 

 

 

자료 조사 출처

 

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

우선순위 큐 - 위키백과, 우리 모두의 백과사전

 

우선순위 큐 (Priority Queue)