우선순위 큐(Priority Queue)

본 포스팅은 윤성우의 열혈 자료구조를 참고했습니다.

 

우선순위 큐는 그 이름이 의미하듯이 큐와 관련이 있다.

하지만 그다지 큐와 관련은 없다.

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

 

우선순위 큐의 특징

• 우선순위 큐는 우선순위를 지니기보다는 데이터를 근거로 우선순위를 판단할 수 있어야 한다. 물론 우선순위의 판단 근거는 프로그래머가 결정할 일이다. 즉 목적에 맞게 우선순위를 결정하면 된다.
• 우선순위가 같은 데이터도 존재할 수 있다.

우선순위 큐의 구현 방법

우선순위 큐를 구현하는 방법은 세 가지가 있다.

 

• 배열을 기반으로 구현하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙을 이용하는 방법

배열을 기반으로 구현하는 법은 두 가지의 단점이 있다.

• 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수 있다.
• 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당겨야 한다.

연결리스트를 이용해 구현하는 경우는 첫 번째의 단점을 같이 갖는다.

 

힙(Heap)이란?

힙은 완전 이진 트리이다. 또한 모든 노드의 데이터는 자식 노드의 데이터보다 크거나 같아야 한다.

힙은 루트 노드에 우선 순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이기 때문에 우선순위 큐의 구현이 간편하다.

 

삽입

 

삭제