우선순위 큐는 이 이름에서 의미하듯이 큐와 관련있어서 "큐"를 확장하는 수준에 마무리 될 것 같지만.. 많은 차이가 있다.

우선순위 큐와 우선순위 이해

큐와 우선 순위 큐는
핵심연산이 enqueue dequeue 로 동일하지만..
연산결과에는 차이가 있다.

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오고
우선 순위 큐는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다."

그렇기에

큐 : 줄서기
우선 순위 큐 : 응급상황

에 빗댈 수 있다.

모든 데이터들이 우선순위를 지녀야 한다기 보다는, 데이터를 근거로 우선순위를 판단할 수 있어야한다.
그리고 우선순위 정보는 대체적으로 정수로 표현되고
낮은게 먼저? 큰게 먼저? 은 결정하기 나름이다.
또한 우선순위는 같은 데이터가 존재할 수 있다.

우선순위 큐의 구현 방법

• 배열
• 연결 리스트
• 힙

배열과 연결리스트로는 매우 구현하기쉽다.

그저 나열하면 되니깐 ! 그런데.. 단점이 따른다.

데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다.

이러한 배열의 단점이 따르지만 이보다 더 큰 문제는

삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야할 수도 있다.

이다.

그렇다면... 연결리스트는 어떨까?
연결리스트는 첫번째 단점은 없지만 마찬가지로 두번째 단점이 존재하기에 우리는!!!

힙

이라는 자료구조를 이용해서 구현할 것이다.

힙이란.

계란 >ㅡ<
ㅎㅅㅎ

힙은 "이진 트리"이되 "완전 이진 트리"이다.
그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값 보다 크거나 같아야한다. 즉 루트 노드에 저장된 값이 가장 커야 한다.

위 문장에서 값 은 우선순위가 된다.
위 문장의 힙을 한번 그러보자 !

위와 같이 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라고 한다.

반면 이와 반대는 "최소 힙" 이라고 한다.

이렇듯 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이다.

이렇듯 힙은 무엇인가를 쌓아 놓은 더미와 흡사하다 하여 지어진 이름이다.
Heap : 무엇인가를 차곡차곡 쌓아 올린 더미 라는 뜻을 지닌다.