우선순위 큐와 힙

10 May 2021

Reading time ~2 minutes

우선순위 큐

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우
스택, 큐, 우선순위 큐 비교
- 스택 : 가장 나중에 삽입된 데이터가 추출
- 큐 : 가장 먼저 삽입된 데이터 추출
- 우선순위 큐 : 가장 우선순위가 높은 데이터 추출
우선순위 큐를 구현하는 방법
- 단순 리스트 이용
- 힙 이용
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일함(힙 정렬)
- 시간복잡도는 O(NlogN)

힙

완전 이진 트리(Complete Binary Tree) 형식을 따름

최소 힙 구성 함수 : Min-Heapify()
- (상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체함

새로운 원소가 삽입되었을 때 O(logN) 시간 복잡도로 힙 성질 유지 가능

원소가 제거되었을 때도 O(logN) 시간 복잡도로 힙 성질 유지 가능
- 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 함
- 이후에 루트 노드에서부터 하향식으로 Heapify() 진행

정리

기존 큐가 넣은 순서대로 빠지는 반면, 우선순위 큐는 넣는 건 동일하되, 빠지는 건 최소, 혹은 최대부터 빠짐.
- 최대부터 빠지는 걸 Max Heap, 최소부터 빠지는 걸 Min Heap

less가 단어 의미상 작은 것부터지만, 나오는 건 큰것부터, greater는 ‘보다 큰’ 이란 뜻이지만, 나오는 건 작은것부터

우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예재

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

void heapSort(vector<int>& arr){
    priority_queue<int> h;

    for(int i=0; i<arr.size(); i++){
        h.push(-arr[i]) // 기본적으로 가장 큰 값이 먼저 나오도록 동작하기에 오름차순 정렬한다면 넣을 때 -를 해줌
    }

    while(!h.empty()){
        printf("%d\n", -h.top()); //반대로 뺄 때는 다시 -를 해줌
        h.pop();
    }
}

int n;
vector<int> arr;

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        scanf("%d", &x);
        arr.push_back(x);
    }
    heapsort(arr);
}

더 맵게(프로그래머스)

#include <string>
#include <vector>
#include <queue>

using namespace std;
priority_queue<int,vector<int>,greater<int>> h; //오름차순 정렬 (1, 2, 3, 4, 5)



int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    for(int i=0; i<scoville.size(); i++){
        h.push(scoville[i]);
    }
    
    
    while(!h.empty()){
        if(h.top() < K){
            if(h.size()==1){
                return -1;
            }
            int p1 = h.top();
            h.pop();
            int p2 = h.top();
            h.pop();
            h.push(p1 + 2*p2);
            answer++;
        }else{
            h.pop();
        }
    }
    
    return answer;
}

Algorithm