우선순위 큐 (Heap) 구현하기

Heap알고리즘으로 백준 1655번 가운데를 말해요를 풀어야하기도 하고, 검색 시스템을 구현할 때 Heap알고리즘을 사용할 예정이었기 때문에 한 번 정리하고자 했다.

#1 우선순위 큐와 Heap의 정의

힙은 자료구조의 형태를 의미한다.

우선순위 큐란 데이터를 큐처럼 추가/삭제할 수 있는 자료구조이면서 동시에, 데이터를 출력할 때 넣은 가중치를 기준으로 높은 우선순위부터 뽑히는 것을 의미한다.

 

우선순위 큐를 구현할 때, 힙 자료구조를 사용하기 때문에 둘을 함께 취급하는 경우가 있다.

 

이름은 queue이지만, 정확히 queue를 사용하는 건 아니고, 트리 형태를 사용한다.

 

#2 힙 자료구조의 특징

최대 힙 - 부모 노드는 자식 노드보다 크거나 같은 값을 가짐.

최소 힙 - 부모 노드가 자식 노드보다 작거나 같은 값을 가짐.

 

완전 이진트리 구조이며, 서브트리도 힙 자료구조를 만족함

 

#3 힙 자료구조에 데이터 추가 과정

1) 일단 완전 이진트리 마지막 위치에 값을 추가

2) 부모 노드가 추가한 노드보다 크면 서로 위치를 바꿔줌 => 이를 반복 (루트에 도달하거나, 부모 노드가 더 큰 경우까지)

 

#4 힙 자료구조 데이터 삭제

"큐" 처럼 특정 위치의 데이터만 삭제 가능한데, 이게 루트 노드가 된다.

이후, 가장 마지막 노드를 루트 노드 자리에 올리고, 노드 추가했을 때 과정과 유사하게 자식 노드와 크기를 비교해서 작으면 아래로 하나 내려주는 과정을 반복한다.

(*이 때 양쪽 자식노드 중 더 큰 값과 바꿔야한다. 작은 값과 바꾸게 되면 나머지 자식노드가 루트로 올라간 노드보다 값이 커지게 때문에 자료구조가 망가지기 때문.)

 

트리의 높이에 비례하는 시간 복잡도를 가지게 되므로, 데이터 추가 삭제가 log2 N 시간 복잡도가 된다.

 

#5 직접 구현해보기

1) 완전 이진트리를 배열로 구하는 아이디어.

struct Node{
    struct Node* left;
    struct Node* right;
};

위와 같이 Node 자료형을 만들어서 동적으로 하나씩 추가해주는 것보다,

 

현재 노드가 i번이라고 할 때, 왼쪽 자식은 i*2, 오른쪽 자식은 i*2 + 1 번 index에 저장하는 논리적인 과정으로

 

완전 이진트리를 구현할 수 있다.

 

최대힙 예시(STL 사용 X)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> heap;

//인자로 index 받기
void swap(int a, int b) {
    int temp = heap[a];
    heap[a] = heap[b];
    heap[b] = temp;
}

void pushHeap(int data, int index) {
    //일단 집어넣고.
    heap[index] = data;

    int temp;

    while (index != 1) {
        if (heap[index / 2] > heap[index]) {
            break;
        }

        swap(index, index/2);

        index = index / 2;
    }
}

int popHeap(int size) {
    int ret = heap[1];
    heap[1] = heap[size+1];

    int index = 1;
    //index * 2 + 1 = 오른쪽 자식이 더 크다고 탈출해버리면 왼쪽 자식이 존재하는 경우 확인을 못할 수 있음.
    int left;
    int right;
    int child;
    while (index * 2 <= size) {
        left = index * 2;
        right = index * 2 + 1;

        //오른쪽 자식이 존재할때
        if (right <= size) {
            //동시에 왼쪽 자식이 더 클때
            if (heap[index * 2] > heap[index * 2 + 1]) {
                //부모가 더 크면 탈출
                if (heap[index * 2] < heap[index]) {
                    break;
                }
                swap(index, index*2);
                index = index * 2;
            }
            //동시에 오른쪽 자식이 더 클때
            else if (heap[index * 2 + 1] >= heap[index * 2]) {
                //부모가 더 크면 탈출
                if (heap[index * 2 + 1] < heap[index]) {
                    break;
                }
                swap(index, index * 2 + 1);
                index = index * 2 + 1;
            }
        }
        else {
            //부모가 더 크면 탈출
            if (heap[index * 2] < heap[index]) {
                break;
            }
            swap(index, index * 2);
            index = index * 2;
        }
        
    }

    return ret;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);

    int num;
    cin >> num;

    heap = vector<int>(num + 1, 0);

    int data;
    int count=0;

    for (int i = 0; i < num; i++) {
        cin >> data;

        if (data == 0) {
            //크기가 0이면,
            if (count == 0) {
                cout << 0 << "\n";
            }
            else {
                count--;
                cout << popHeap(count) << "\n"; 
            }
        }
        else {
            count++;
            pushHeap(data, count);
        }
    }

    return 0;
}

 

 

STL을 통해서 구현하는 예시

 

queue 라이브러리에 있고 priority_queue<자료형> pq; 형식으로 선언할 수 있다.

(c++ 에서 pq 라이브러리는 루트노드가 가장 큰 값이 오는 최대 힙이 기본으로 설정되어 있기 때문에 최소힙으로 만들어주고 싶으면 데이터에 -를 붙혀서 저장할때만 데이터의 크기를 바꾸는 등의 방법을 사용해야함.)

 

queue와 거의 유사한 구조의 메소드를 가지고 있다.

 

push() pop() top() empty() size() 이다.

 

 

백준 문제 "가운데를 말해요"로 정리해보자.

 

최대값과 최소값을 구하는 두 힙을 같이 사용해서 중앙값을 구하는 방법을 사용하는 알고리즘 문제이다.

 

중앙값보다 작거나 같은 값들을 저장하는 최대힙과

중앙값보다 큰 값을 저장하는 최소힙을 만들어 주는게 포인트이다.

 

마치 모래시계 같은 구조가 되는데, 최대힙에 항상 먼저 데이터를 넣어준다고 가정할 떄, 최대힙의 루트에 중앙값이 오게된다.

 

다만 데이터를 한번 넣을 때 마다, 힙 push를 수행하고, 루트노드를 비교하여 값을 바꾸던가 그렇지 않던지의 과정을 추가한다. 이는 데이터가 한 개 들어올때마다 한번의 '밀림'으로 중앙값이 결정됨을 보면 알 수 있는 알고리즘이다.

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);

    priority_queue<int> maxHeap;
    priority_queue<int> minHeap;

    int num;

    cin >> num;

    int temp;

    //그냥 넣을 첫번째.
    cin >> temp;
    maxHeap.push(temp);
    cout << maxHeap.top() << "\n";

    for (int i = 1; i < num; i++) {
        cin >> temp;

        //일단 단순히 넣기
        if (i % 2 == 0) {
            maxHeap.push(temp);
        }
        else {
            minHeap.push(-temp);
        }

        
        int swapTemp;
        //비교. 평균 이하의 최대가 평균 이상의 최소보다 큰 경우
        if (maxHeap.top() > -minHeap.top()) {
            swapTemp = maxHeap.top();
            maxHeap.pop();
            maxHeap.push(-minHeap.top());
            minHeap.pop();
            minHeap.push(-swapTemp);
        }

        cout << maxHeap.top() << "\n";
    }

    return 0;
}

 

 

#6 priority_queue 비교 함수 커스텀하기

다음은 info 구조체 내부의 변수를 기준으로 비교하는 priority_queue를 만들고 싶을 때 사용하는 방법이다.

struct info {
    int start;
    int term;
};

struct compare {
    bool operator()(info& num1, info& num2) {
        return num1.start < num2.start;
    }
};

 

비교하는 struct compare 선언. 특이하게 ()() 두개의 구조로 되어 있다.

    //custom heap 만들기
    priority_queue<info, vector<info>, compare> startHeap;

 

위와 같은 구조로 선언한다. 두번째 인자에 vector<사용하려는 자료형>, 세번째 인자에 위에서 선언한 compare가 온다.

 

풀었던 디스크 컨트롤러

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>


using namespace std;

bool cmp1(vector<int>& vc1, vector<int>& vc2) {
    return vc1[0] < vc2[0];
}

struct cmp2 {
    //내림차순
    bool operator()(vector<int> v1, vector<int>v2) {
        return -v1[1] < -v2[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    //길이를 기준으로 시작 시간이 지날때마다 heap에 넣음.
    sort(jobs.begin(), jobs.end(), cmp1);


    priority_queue<vector<int>, vector<vector<int>>, cmp2> workHeap;
    vector<int> time;

    workHeap.push(jobs[0]);
    int count = 1;

    while (jobs.size() < count && jobs[0][0] == jobs[count][0]) {
        workHeap.push(jobs[count]);
        count++;
    }

    int endTime;
    int startTime = 0;

    while (!workHeap.empty()) {
        endTime = startTime + workHeap.top()[1];
        time.push_back(endTime - workHeap.top()[0]);

        workHeap.pop();

        for (int i = count; i<jobs.size() && endTime >= jobs[i][0] ; i++) {
            workHeap.push(jobs[i]);
            
            count++;
        }
        startTime = endTime;

    }
    int sum = 0;
    for (int i = 0; i < time.size(); i++) {
        sum = sum + time[i];
    }

    answer = sum / time.size();

    cout << answer;

    return answer;
}

int main() {
    solution({ {0,3}, {1,9}, {2,6} });
}