[자료구조] 우선순위 큐(Priority Queue)

우선순의 큐에 대해 알아보자.

큐(Queue) 라고 하면 흔히 먼저 들어온게 먼저 나간다는(First in First out)구조이다.

하지만 우선순위 큐(Priority Queue) 는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 의미한다.

 

우선순위 큐는 힙(Heap) 이라는 자료구조를 가지고 구현할 수 있다.

우선순위 큐는 배열을 이용해 구현할 수 있고, 

연결리스트, 힙 기반 으로도 구현할 수 있다.

 

들어가기 전 각 기반에 따른 시간 복잡도에 대해 알아보자.

배열 기반 삽입 : O(n)

배열 기반 삭제 : O(1)

 

힙 기반 삽입 : O(log2n)

힙 기반 삭제 : O(log2n)

 

 

그럼 본격적으로 시작해 보겠다.

힙(Heap) 은 완전 이진 트리를 배열로 만든 자료구조이다.

이는 기존 트리와는 다르게 우선순위가 적용된다.

우선순위는 프로그래머가 임의대로 조정할 수 있다. 

 

만약 1부터 10까지를 완전 이진 트리를 이용해 구현한다고 하자.

대충 이렇게 생겼다고 가정 하자.

여기서 이진트리에서 삽입이 발생했을 때의 과정은 생략하고, 

우선순위가 적용된 상태에서 삽입과 삭제가 되는 과정을 설명하겠다.

 

우선순위는 최대 힙(max heap) 과 최소 힙(min heap)으로 구성할 수 있다.

 

먼저 최대 힙이란?

부모 노드가 자식노드보다 값이 큰 완전 이진트리를 의미한다.

모든 부모 노드가 자식보다 값이 커야한다.

최대힙의 루트 노드는 항상 최댓값을 가진다.

=> 루트 노드로 올라갈 수록 값이 커지는 구조이다.

 

 

먼저, 최대 힙(max heap)는 어떻게 생겼는지 확인해 보도록 하자.

다음을 보면 루트 노드(root node) 가 10으로 원소 중 가장 큰 값을 가지고 있는 것을 확인할 수 있다.

또한, 부모 노드는 자식 노드보다 값이 더 크다는 것 또한 확인할 수 있다. 

 

 

 

 

 

다음으로는 최소 힙(min heap) 은 최대 힙(max heap) 과는 정 반대로

루트 노드와 부모 노드가 가장 작은 값을 지니게 된다. 

=> 루트 노드로 올라갈 수록 작은 수를 지니게 된다.

 

대충 그림을 그려보면

위와 같다.

 

 

이상으로 최대 힙과 최소 힙에 대해 알아보았다.

 

다음으론 만약 값이 삽입 되었으면 어떠한 형태로 삽입되는지 알아보자.

최대 힙에서 20이 들어간다고 가정해보자.

다음과 같이 변한다.

 

여기서 최소 힙은 이와 반대라고 생각하면 된다.

 

다음은 삭제의 과정이다. 

1~10 까지 존재하는 최대 힙(max heap) 에서 원소 1개를 삭제한다고 가정해 보자.

여기서 삭제하는 것은 힙(heap) 에서 pop 한 것과 같다.

만약 위의 트리에서 1개를 pop 하게 되면 루트 노드(root node) 를 삭제하는 것과 동일하다.

 

 

 

다음과 같이 정렬된다