[자료구조] 우선순위 큐 - 작성 중

큐는 FIFO, 우선순위 큐는 우선순위가 높은거 먼저 나옴

 

구현

1. 리스트를 이용한 구현 (큐로도 가능?)

2. 힙을 이용한 구현

 

시간 복잡도

1 -> 0(1), 삭제 시는 O(N) // 찾아서 삭제해야됨

2. -> O(log N) / O(log N) -> 삽입 삭제가 시간복잡도 동일하고

데이터의 입출력 과정이 힙정렬과 동일, 이때는 O(N log N)

 

힙은 완전 이진트리의 일종, 항상 루트 노드 제거

최소 힙은 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선 제거됨

ㄴ 넣었다 빼면 걍 오름차순

최대 힙은 루트 노드가 가장 큰 값이고 값이 가장 큰 데이터가 우선 제거됨, 내림차순

 

완전이진트리 : 루트부터 왼쪽, 오른쪽으로 순서대로 데이터가 삽입되는 트리

 

최소힙 구성함수 (min-heapify()), 상향식과 하향식으로 구현 가능, 최소 힙 성질을 만족하지 않는 서브 트리를 만족하도록 만들어 주는 함수, 새로운 원소 삽입 시 O(log N) 으로 힙 성질을 유지 가능

 

c++에서는 priority_queue 제공 가장 큰 값이 먼저 나오도록 동작함-> 오름차순으로 하려면 -를 붙여 부호를 반대로 바꿔줌

#include<bits/stdc++>

using namespace std;

void main(){
    priority_queue<int>& h;
    
    // 내림차순 (기본은 루트 노드가 가장 큰값을 가짐)
    h.push(1);
    h.push(3);
    
    // 오름차순 (부호가 반대면 1이 위로 올라감, 꺼낼때도 -붙여주기)
    h.push(-1);
    h.push(-3);
    
    h.top();
    // 오름차순 시 -h.top();
    
    h.pop();
}

 

 

priority_queue

push, pop, top, empty, size 제공

 

#include <queue>

내림차순(가장 큰값부터 출력) 시 priority_queue<int> pq;

 

#include <functional> // -> less, greater 

가장 작은 값부터 pop, 오름차순으로 사용 시 priority_queue<int, vector<int>, less<int>> pq;