[C++][STL][자료구조] 힙(Heap), 우선순위 큐(Priority queue) (feat. stack, queue, deque)

* Heap(힙)

: 최대값/최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 형태의 자료구조

(완전 이진 트리: 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있고, 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조)

: 삽입/삭제/최대값 찾기/최소값 찾기에 걸리는 시간복잡도 O(logN)

: root가 최대 값을 갖는 최대 힙(Max Heap)과 root가 최소 값을 갖는 최소 힙(Min Heap)이 있음

: 값이 '왼쪽 자식 < 부모 < 오른쪽 자식' 순으로 크기가 큰 이진 탐색 트리(Binary Search Tree)와 달리 '자식 < 부모' 형태의 값 크기만 유지됨.

: Heap 자료구조를 응용한 대표적인 예) Priority queue(우선순위 큐)

 

 

* priority queue(우선순위 큐)

:  priority_queue<자료형, 구현체, 비교연산자> 로 정의

   1) 자료형은 int, double 등으로 지정가능

   2) 구현체의 기본은 vector<자료형> 으로 정의된다.

   3) 비교 연산자의 default값은 less<자료형>으로 내림차순 정렬이고, greater<자료형>을 넣어서 오름차순 정렬로 만들 수 있다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    //우선순위 큐 내림차순
    priority_queue<int> pq_less;
    
    pq_less.push(1);
    pq_less.push(5);
    pq_less.push(3);
    int pq_less_size = pq_less.size();
    for(int i=0; i<pq_less_size; i++){
       cout << pq_less.top() << " "; // 5 3 1
       pq_less.pop();
    }cout << "\n";
    
    
    //우선순위 큐 오름차순
    priority_queue<int, vector<int>, greater<int>> pq_greater;
    
    pq_greater.push(1);
    pq_greater.push(5);
    pq_greater.push(3);
    int pq_greater_size = pq_greater.size();
    for(int i=0; i<pq_greater_size; i++){
       cout << pq_greater.top() << " "; // 1 3 5
       pq_greater.pop();
    }
	
    return 0;
}

 

: pair와 함께 사용하면, 인자가 여러 개일 때 정렬도 한번에 구현 가능하다. pair의 first를 먼저 비교하고 first값이 같을 경우 second 값을 비교하여 정렬 및 저장되기 때문이다.

#include <iostream>
#include <queue>
using namespace std;

int main(){
   priority_queue<pair<int, int>> pq;
   
   pq.push(make_pair(10, 100));
   pq.push(make_pair(1, 50));
   pq.push(make_pair(1, 200));
   pq.push(make_pair(50, 50));
   pq.push(make_pair(-10, 200));
   
   int pq_size = pq.size();
   for(int i = 0; i < pq_size; i++){
      cout << pq.top().first << " " << pq.top().second << "\n";
   }
   return 0;
}

 

[C++ official reference 참조]

priority_queue::priority_queue - C++ Reference

 

cf) stack, queue, deque

*stack: 선입선출구조로 뒤로 데이터를 추가하고 앞으로 데이터를 제거하는 자료구조

        : push(), pop(), top(), empty(), size() 등의 함수 사용

#include <stack>

int main(){
    stack<int> stk;
    
    stk.push(1); // 1
    stk.push(2); // 1 2
    stk.push(3); // 1 2 3 
    
    stk.pop(); // 2 3
    
    stk.top(); // 2
    
    return 0;
}

 

* queue: 후입선출구조로 뒤로 데이터의 추가/삭제가 가능한 자료구조

          : push(), pop(), front(), back(), empty(), size() 등의 함수 사용

#include <queue>

int main(){
    queue<int> q;
    
    q.push(1); // 1
    q.push(2); // 1 2
    q.push(3); // 1 2 3 
    
    q.pop(); // 1 2 
    
    q.front(); // 1
    q.back(); // 2
    
    return 0;
}

 

* deque: 뒤로만 추가/삭제가 가능한 queue, vector와 달리, 앞/뒤로 추가/삭제가 가능한 자료구조.

           : push_back(), push_front(), pop_back(), pop_front(), front(), back(), empty(), size(), clear() 등의 함수 사용

#include <deque>

int main(){
    deque<int> dq;
    deque<int> dq2(10); // defualt(0) 값으로 초기화된 10개의 원소를 가진 deque 생성
    deque<int> dq3(10, 1); // 1로 초기화된 10개의 원소를 가진 deque 생성
    deque<int> dq4(dq3); // dq3을 복사한 dq4 생성
    
    dq.push_back(1); // 1
    dq.push_back(2); // 1 2
    dq.push_back(3); // 1 2 3 
    dq.push_front(0); // 0 1 2 3
    
    dq.pop_back(); // 0 1 2    
    dq.pop_front(); // 1 2
    
    dq.front(); // 1
    dq.back(); // 2
    
    return 0;
}