[C++] 우선순위큐 - 최대힙, 최소힙

우선순위큐(priority queue)

우선순위큐(default 최대 힙)는 삽입된 요소에 대해 우선순위가 높은 데이터를 먼저 가져오는 형식의 자료구조다. 우선순위큐는 주로 힙 자료구조를 기반으로 구현된다.

 

힙(heap)

• 힙은 완전이진트리의 일종으로 우선순위큐를 위해 만들어진 자료구조다.
• 최대값/최소값을 빠르게 찾아내도록 만들어졌다.
  • 최대힙에서는 최대값, 최소힙에서는 최소값을 O(1)의 시간복잡도로 빠르게 접근할 수 있다.
  • 삽입과 삭제 연산은 트리의 높이에 비례하기 때문에 O(log N)의 시간복잡도를 가진다.
• 이진탐색트리에서는 중복된 값을 허용하지 않는 반면 힙 트리에서는 중복된 값을 허용한다.
• 힙은 최대힙과 최소힙 형태로 나뉜다.
  •  최대힙
    • 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전이진트리
    • 부모노드의 키 값 >= 자식노드의 키 값
  •  최소힙
    • 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전이진트리
    • 부모노드의 키 값 <= 자식노드의 키 값
     

 

C++ 우선순위큐 구현

#include <queue>

priority_queue<int> pq; // 최대힙
priority_queue<int, vector<int>, greater<int> > pq; // 최소힙

pq.push(1); // 원소 추가
pq.pop(); // 원소 삭제
pq.top(); // 루트 노드 조회
pq.empty(); // 비어있는지 확인
pq.size(); // 원소 개수 반환

 

priority_queue<자료형 T> 또는 priority_queue<자료형 T, 구현체 컨테이너, 비교 연산자> 형태로 우선순위큐를 선언한다. 비교 연산자는 기본적으로 오름차순(greater<T>)과 내림차순(less<T>)을 사용하지만 다른 비교 연산자도 설정할 수 있다.

 

관련 알고리즘 문제: 백준 1927, 11279