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

■ 이론

우선 순위 큐는 힙 트리(Heap Tree)의 구조를 갖는다. 최적 조건에 해당하는 값을 한 번에 구하고 싶을 때 유용한 자료구조이다.

 

연결리스트나 벡터 같은 경우 최대값 최소값을 찾으려면 O(n)만큼 선회하며 모든 값을 비교해줘야 도출할 수 있다.

 

하지만 우선순위큐는 힙트리의 구조로인하여 완전이진트리의 형태를 띄고 있다. 데이터를 삭제 및 추가하는 과정에서 대소관계를 비교하며 노드를 이동시키는 연산이 트리의 높이(logN)만큼 발생하므로 O(logN) 정도의 시간복잡도로 수행된다.

 

[힙트리 설명 및 힙 정렬 알고리즘은 아래 포스팅에서 이전에 C#으로 구현해봤었다.]

https://yjhdevelopdiary.tistory.com/172

[Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 비교표

 

■ 코드

기본적인 뼈대는 아래와 같다. template(C#에선 Generic)으로 컨테이너가 담을 데이터의 형태를 일반화 시켜주고 두번째 타입네임에는 조건식(Predicate)을 받아줌으로써 최소힙(Min Heap) and 최대힙(Max Heap)을 따로따로 구현해줄 필요 없이 하나의 컨테이너에서 원할때마다 최소값, 최대값을 반환받을 수 있다.

 

삭제 과정과 삽입 과정은 위 포스팅에서 정리되어 있다. 주석으로 시간복잡도를 쓰는 것은 익숙해질려고 연습하고 있는 중이라서 작성하게 되었다.

 

[Whole Features]

 

 

[Sub Functions]

 

 

※ C#과 C++의 차이

T& top과 void Pop()을 따로 두는 것이 C++ 표준이라는 점에 많이 놀랐다. C#에선 Pop과 동시에 반환값으로 삭제된 데이터를 반환해주는데 C++에선 메모리를 개발자가 직접 관리해주면서 그 와중에 멀티 쓰레딩을 하다보니 어떤 일이 발생할지 몰라 예외 처리를 위해 T& top()을 통해 값을 반환받은 뒤 pop()함수로 제거해준다고 한다. 예시는 아래 Pop()함수를 보면 된다.

 

[Push]

[Pop]

 

 

[추가]

표준 컨테이너 라이브러리를 확인해보면 priority_queue의 구조는 위와 같이 vector리스트로 데이터를 담는 것이 기본값이지만 원한다면 다른 종류의 컨테이너로 담을 수 있다.

▼ 이미지