[C++] STL #4 힙, 우선순위 큐 (Heap, Priority_queue)

목차

※ STL #1 순차 컨테이너

※ STL #2 연관 컨테이너

※ STL #3 Stack & Queue

 

1. Heap

2. Priority_queue

 

---

1. Heap

- 완전 이진 트리 (Complete Binary Tree) 기반 자료구조

ㄴ 이진 트리 : 자식 노드가 최대 두 개인 노드들로 구성된 트리

ㄴ 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 이진 트리

     ※ 마지막 레벨은 왼쪽 부터 순차적으로 채워져야한다.

 

- 최대값 혹은 최소값을 빠르게 구하기 위한 자료구조

- 부모 자식 간의 관계만 중요하고 형제 노드와는 관계성이 없다.

- Min Heap : 부모 노드가 자식 노드보다 항상 작다 (= 루트 노드가 최소값이다)

- Max Heap : 부모 노드가 자식 노드보다 항상 크다 (= 루트 노드가 최대값이다)

 

Max Heap 예시

0123456789

Max Heap 에서 루트 노드 추출 예시

 

 

2. std::Priority_queue

- Heap(힙) 자료구조를 기반

-임의로 설정된 우선 순위를 기준 (Heap 는 최대 최소만 가능)

 

가. 선언 및 초기화

template<typename T>       // template ≒ 자유 자료형

std::priority_queue<T>         //T : 배열에 담길 자료형

 

- priority_queue<int> pq1;                                     // 빈 우선순위 큐 생성

-  vector<char> v{ 'a', 'b', 'c' };
    priority_queue<char> pq2(v.begin(), v.end());   // 벡터나 데크를 이용하여 초기화 가능

- priority_queue<char> pq3(pq2)                           // pq2를 복사하여 pq3 생성

 

나. 멤버 함수 ( ※ 기준 :  vector<int> v{ 1, 2, 3, 4 };      priority_queue<int> pq(v.begin(), v.end()); ) 

Element access(요소 접근)
pq.top()	최상위 요소를 반환한다. (예시 기준 4)
Capacity(용량)
pq.empty()	큐가 비어있는지 확인하고 bool 값 반환
pq.size()	큐의 크기를 반환한다.
Modifiers(수식어)
pq.push(num)	큐에 num을 삽입한다. (삽입 때 마다 자동 정렬 됨)
pq.emplace(num)	큐에 num을 삽입한다. (삽입 때 마다 자동 정렬 됨)
pq.pop()	최상위 요소를 제거한다.
pq.swap(pq2)	pq와 pq2의 인자를 교환한다.

 

다. 우선 순위 정하기

- 기본 생성은 최대값을 기준으로 정렬한다.

- std::priority_queue<자료형, 구조체, 비교 연산자> 형태로 원하는 값을 기준으로 우선 순위를 정할 수 있다.

 

1) 기본 비교 연산자 (최소, 최대)

- priority_queue<int, vector<int>, greater<int> > pq : 최소값 기준

- priority_queue<int, vector<int>, less<int> > pq2 : 최대값 기준

 

2) 비교 연산자

- 직접 비교 기준을 만들 수도 있다.

- 구조체로 만들어짐

- bool operator()에서 return 값이 true면 swap가 실행된다

ㄴ ex) a(부모노드) > b(자식노드) 라면 작은 수인 자식 노드가 루트노드 쪽으로 올라가게 된다.

ㄴ 즉, 최소값 정렬이 된다.

절대값 최소 기준 예시

 

3) 구조체 활용 (우선순위 결정 요소가 다양할 경우)

- 비교할 변수가 여럿일 경우 구조체로 자료형을 만들고 비교하여 우선순위 결정 가능

나이 기준 정렬, 나이가 같다면 이름 순 정렬

 

※ 참조

c++ reference : https://en.cppreference.com/