자료구조 우선순위큐(Priority Queue) 기초 개념 정리

우선순위큐(Priority Queue)

우선순위큐는 선입선출인 큐와는 다르게 이름 그대로 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 

우선순위의 판단기준은 데이터에 근거하며, 목적에 맞게 우선순위를 결정해야 한다.

우선순위큐 구현 방법: 배열기반, 연결리스트기반, 힙(Heap)기반

우선순위큐는 배열 및 연결리스트 보다는 힙으로 구현하는 것이 가장 바람직하다. 

힙을 사용해야 이유: 배열과 연결리스트는 우선순위가 낮은 데이터를 삽입할 경우 모든 데이터와 우선순위를 비교해야 한다. 하지만 힙을 사용하면 삽입과 같은 과정을 진행할때 대부분 부모노드와 자식노드사이에서 비교연산이 이루어지기 때문에 힙은 트리의 높이 만큼 비교연산을 진행하면 된다.

->힙을 사용하여 우선순위큐 구현(우선순위큐는 추상적인 개념)

우선순위큐 ADT

PQueueInit: 우선순위큐의 초기화를 수행하며, 가장 먼저 호출해야한다.

PQIsEmpty: 우선순위큐가 비어있는지 확인하는 함수이다.

PEnqueue: 우선순위큐에 데이터를 저장하는 함수이다.

PDequeue: 우선순위가 가장높은 데이터를 삭제 및 반환한다. 

---

힙(Heap)

힙이란 완전이진트리이며, 루트노드에 저장된 값이 가장크며 모든 노드들이 자식노드 보다 값이 큰 최대힙(Max Heap) 과 반대로 루트노드로 올라갈수록 값이 작아지는 최소힙(Min Heap)이 있다.

힙의구현은 배열로 하는 것이 바람직하다. (연결리스트로 구현하면 새로운 노드를 힙의 마지막 위치에 삽입하는 것이 어렵다.)

자식노드의 인덱스 값을 얻는 방법의 필요성 -> 힙에서 데이터 삭제를 위함

부모노드의 인덱스 값을 얻는 방법의 필요성 - > 힙에서 데이터 추가를 위함

루트노드로 올라갈수록 값이 작아지는 최소힙의 경우

왼쪽자식노드인덱스 = 부모노드의인덱스 * 2

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

부모노드인덱스 = 자식노드의 인덱스 / 2