우선순위 큐는 왜 힙 구조를 사용할까?

우선순위큐에 대해 설명하기 전에 힙에 대해 간단히 정리해보면, 

힙은 완전 이진트리의 형태이며 루트노드가 최대값(max-heap기준)이고, 삽입 삭제의 연산이 logN인 특징을 갖는다. 

 

그렇다면 우선순위큐란 뭘까?

기존에 큐(Queue) 자료구조는 넣은 순서대로 출력이 되었다면,

우선순위큐는 기준을 스스로 정할 수 있는것이다. 

 

여기서 기준이란? 

데이터를 입력한 자료구조에서 빼내올때 출력되는 순서의 기준을 뜻한다. 

큐의 경우 입력순서가 될 것이다. 

 

 

 

 

---

 

 

 

다시 본론으로 돌아와서 우선순위큐를 구현할 수 있는 자료구조는 많이 있는데 

왜 하필 우선순위큐는 힙 구조를 사용할까? 

이유는 수행시간 때문이다. 

 

노드(데이터)수를 N이라고 했을때 heap은 삽입 삭제 연산이 모두 logN이지만

배열, 리스트와 같은 선형구조의 형태는 삽입 혹은 삭제 둘중하나의 연산이 극단적인 수행시간을 갖는다.

 

정렬이 되어있지 않은 배열과 리스트의 경우, 입력은 아무것도 따질것이 없으므로 상수 수행시간을 갖는다. 

반면, 우선순위에 부합하는 원소를 찾는 과정에서는 최악의 경우 n번의 연산을 통해 찾아낼 수 있다. 

 

정렬이 되어있는 배열과 리스트의 경우, 입력하는 과정에서 정렬을 시켜야한다. 따라서 최악의 경우 n번의 연산을 수행한다. 정렬이 되어있으므로 우선순위에 부합하는 원소를 찾는 과정은 상수시간에 가능하다. 

 

 

 

자료구조와 알고리즘에서는 항상 최악의 상황을 고려해야 하는데 만약 n개의 데이터 모두 최악의 경우에 놓인다면??

그럼 n^2(n의 제곱)의 수행시간을 갖게된다. 

 

 

반면 힙의 경우, 삽입 삭제 모두 최악의 경우 logn의 수행시간을 갖기 때문에 n개의 데이터 모두 최악의 상황에 놓인다고 가정해도 nlogn이 수행시간을 갖는다. 데이터의 크기가 커질수록 n^2과 nlogn은 엄청난 차이를 갖는다. 

 

 

이러한 이유 떄문에 우선순위큐는 힙의 구조를 통해 구현한다.