우선순위 큐(Priority Queue) 개념 (1)

우선순위 큐(Priority Queue) 란?

이전에 배워온 큐는 선형 자료구조이지만, 우선순위 큐(Priority Queue)는 비 선형 자료 구조이다.

우선순위 큐(Priority Queue)는 들어가는 순서에 관계없이 큐에서 dequque 될 때, 우선순위에 맞게 나간다.

이때 우선순위 큐의 우선순위는 프로그래머가 결정한다.

예를들어 A,B,C가 있을 때, A가 우선순위가 1, B가 3, C가 2면

C, B, A순으로 넣어도 A, C, B순으로 나온다.

우선순위 큐의 연산은 크게 두가지로 나뉜다.

enqueue :: 우선순위 큐에 데이터를 삽입

dequeue :: 우선순위 큐에서 데이터를 꺼내기

우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만, 

배열은 공간의 낭비가 심해지고, 어느정도의 노드가 필요할지 알 수 없게 되니 좋지 않다.

또한 배열을 이용할 시 순차적으로 우선순위대로 넣으면 되지만, 우선순위가 변경되거나 할 때 배열에서 서로 값들이 움직여야되는 동작들이 발생하기에 

많은 부하가 발생한다.('오버헤드가 일어난다' 라고도 한다.)

그리고 연결 리스트 또한 배열과 마찬가지의 방식이기에 이 게시물에서는 힙(heap)을 이용한 우선순위 큐를 설명한다.

참고로 시간 복잡도는 다음과 같다.

배열 기반 데이터 삽입의 시간 복잡도 : O(n)

배열 기반 데이터 삭제의 시간 복잡도 : O(1)

연결 리스트 기반 데이터 삽입의 시간 복잡도 : O(n)

연결 리스트 기반 데이터 삭제의 시간 복잡도 : O(1)

힙 기반 데이터 삽입의 시간 복잡도 : 

힙 기반 데이터 삭제의 시간 복잡도 :