우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐(Priority Queue)는 완전이진트리인 힙(Heap)으로 구현되어 있다.

 

 

우선순위 큐(Priority Queue)

큐(Queue)는 FIFO(First in - First out)구조로 먼저 들어온 데이터가 먼저 나가는 구조이다.

우선순위 큐(Priority Queue)는 들어온 순서와는 무관하게 우선순위가 높은 데이터가 먼저 나가는 구조이다.

데이터가 들어오면 우선순위에 따라 자동으로 정렬한다.

 

때문에 우선순위 큐는 우선순위에 따라 정렬하는데 효율적인 힙(Heap)을 이용하여 구현한다.

- 힙이 아닌 배열로 구현했다고 가정하자.

데이터를 삽입하면 우선순위에 따라 정렬하기 위해 모든 인덱스를 탐색해야 한다.

여기서 시간복잡도는 데이터가 n개 일 때 O(n)이 된다.

연결리스트도 마찬가지이다.

 

- 그럼 힙을 사용한 이유는 뭘까?

힙의 경우 완전이진트리로 부모와 자식간의 비교만 계속 이루어진다.

즉, 직접적으로 연결된 데이터만 비교하게 되는 것이다.

이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산횟수는 1회 증가한다.

여기서 시간복잡도는 O(log2n)이 된다.

배열과 연결리스트의 경우, index가 존재하기 때문에 삭제는 매우 빠르다. 하지만 삽입의 경우 비효율적이다.

삭제 측면에서는 배열/연결리스트가 우위를 점할지라도, 삽입 측면에서는 힙의 시간복잡도가 월등하기 때문에

편차가 심한 배열/연결리스트 보다는 힙을 사용하여 구현한다.

 

힙(heap)

- 힙은 완전이진트리(Complete Binary Tree)다.

- 모든 노드는 자식노드들 보다 우선순위가 크거나 같다. (중복값이 허용되므로 우선순위가 같을 수 있다.)

- 루트 노드의 우선순위가 가장 높다.

최대 힙(Max Heap) : 부모노드 키 값이 자식노드보다 크거나 같은 완전이진트리

최소 힙(Min Heap) : 부모노드 키 값이 자식노드보다 작거나 같은 완전이진트리