[Heap, 난이도 중] 프로그래머즈, 이중우선순위큐

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리이다.

삽입, 삭제의 시간 복잡도가 O(logn) 밖에 안된다.

 

구조를 최대 힙 기준으로 간단히 설명 해보자면 이렇다.

삽입 : 처음에는 힙의 마지막 인덱스에 두고 부모 노드보다 클 경우 계속해서 부모 노드와 swap 해나가면 된다. 

삭제 : 힙의 마지막 인덱스를 root에 두고 두 자식 노드들중 큰 값을 가지는 노드와 swap해나가면 된다.

더 자세한 설명이 필요하다면 위키백과를 확인해보면 좋다.

ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

 

이 문제에서는 최대 힙, 최소 힙 구조 모두 필요하다.

C++ 에서는 <queue> 헤더에서 이 힙 구조를 제공하는 priority_queue가 있다.

 

이 포스팅에서 첨부한 소스 코드는 2개이고, 모두 만점을 받은 소스 코드이다.

 

첫 번째 소스 코드는 최대 힙, 최소 힙 모두 우선 순위 큐를 사용한 코드,

두 번째 소스 코드는 최대 힙은 직접 구현하고, 최소 힙만 우선 순위 큐를 사용한 코드이다.

힙 구조를 손코딩 할 수 있는지 물어보는 기업도 있다고 들어서, 최대 힙만큼은 직접 구현도 해보려는 의도였다.

 

최댓값, 최솟값을 제거 할 때 두 힙은 서로 연동이 되어야 한다.

최댓값을 제거할 경우에는 최대 힙 뿐만 아니라 최소 힙의 크기도 -1 되어야 한다는 것이다.

이러한 경우에는 모든 operations 자체에 대해 count를 하면 된다.

입력이 들어올 경우 +1, 요소가 제거되었을 경우 -1를 해주고, count가 0이 되는 순간 최대 힙, 최소 힙을 모두 지워주면 된다.

최소 힙같은 경우에는 우선 순위 큐를 다시 선언하여 힙을 초기화 시켰다.

 

1. [최대 힙, 최소 힙 모두 priority_queue 라이브러리 사용]

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
priority_queue<int,vector<int>,greater<int> > minpq;
priority_queue<int,vector<int>,less<int> > maxpq;
int heap_size=0;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    for(int i=0;i<operations.size();i++){
        if(operations[i][0]=='I'){
            int push = stoi(operations[i].substr(2));
            minpq.push(push);
            maxpq.push(push);
            heap_size++;
        }
        else if(operations[i][2]=='-' && heap_size!=0){ //최솟값
            heap_size--;
            if(heap_size==0) {
                minpq=priority_queue<int,vector<int>,greater<int> >();
                maxpq=priority_queue<int,vector<int>,less<int> >();
            }
            if(!minpq.empty()) minpq.pop();
        }
        else if(heap_size!=0){ //최댓값
            heap_size--;
            if(heap_size==0) {
                minpq=priority_queue<int,vector<int>,greater<int> >();
                maxpq=priority_queue<int,vector<int>,less<int> >();
            }
            if(!maxpq.empty()) maxpq.pop();                          
        }
    }
    if(heap_size==0){
        answer.push_back(0);
        answer.push_back(0);
        return answer;
    }
    answer.push_back(maxpq.top());
    answer.push_back(minpq.top());
    return answer;
}

 

2. [최대 힙은 직접 구현, 최소 힙은 priority_queue 라이브러리 사용]

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int heap[1000001];
priority_queue<int,vector<int>,greater<int> > pq; //최솟값 추출용
int heap_size=0;
vector<int> solution(vector<string> operations) {
    vector<int> answer;
    int root, node;
    for(int i=0;i<operations.size();i++){
        root=0;
        node=0;
        if(operations[i][0]=='I'){
            int push = stoi(operations[i].substr(2));
            pq.push(push);
            heap[heap_size]=push;
            heap_size++;
            node = heap_size-1;
            while(node!=0){
                root = (node-1)/2;
                if(heap[node]>heap[root]){
                    int temp = heap[node];
                    heap[node] = heap[root];
                    heap[root] = temp;
                }
                else break;
                node=root;
            }
        }
        else if(operations[i][2]=='-' && heap_size!=0){ //최솟값 제거
            heap_size--;
            if(heap_size==0) pq=priority_queue<int,vector<int>,greater<int> >();
            if(!pq.empty()) pq.pop();
        }
        else if(heap_size!=0){ //최댓값 제거
            int temp = heap[heap_size-1];
            heap[heap_size-1] = heap[0];
            heap[0] = temp;
            heap_size--;
            while(heap_size!=0){
                if(heap_size<2*(root+1)) break;
                else if(heap_size==2*(root+1)) node=2*root+1;
                //같은 결과라도, 가독성을 위해 분리
                else if(heap[2*root+1]>heap[2*root+2]) node=2*root+1;
                else node=2*root+2;
                int temp = heap[node];
                heap[node] = heap[root];
                heap[root] = temp;
                root=node;
            }                               
        }
    }
    if(heap_size==0){
        answer.push_back(0);
        answer.push_back(0);
        return answer;
    }
    sort(heap,heap+heap_size);
    answer.push_back(heap[heap_size-1]);
    answer.push_back(pq.top());
    return answer;
}

 

2개 소스 코드 모두 만점