[C++] 백준 1927번 : 최소 힙 (S1) &11279번 : 최대 힙 (S2)

#문제

www.acmicpc.net/problem/1927

1927번: 최소 힙

www.acmicpc.net/problem/11279

11279번: 최대 힙

#풀이

Min/Max heap을 구현해야 하는 문제들이다. 힙은 배열을 통해 구현했고, 인덱스는 1부터 사용했다. 이를 통해 어떤 노드의 index가 i일 때, 부모 노드의 index는 (i/2)이고, 좌측 자식 노드의 index는 (2*i), 우측 자식 노드의 index는 (2*i+1)가 된다. 풀이 중 시간초과가 발생했지만 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)을 추가하여 해결했다. push후 재정렬할 때는 형제노드를 고려할 필요가 없었지만, pop후 재정렬 할때는 형제노드를 고려해 주어야 했다. 또한, pop후 재정렬에서의 반복문은 좌측 자식 노드가 존재하는 한 반복문이 수행되도록 설정했다. 마지막에 실수했던 것은 pop후 재정렬에서 우측 자식 노드와 swap을 한 후 다음에 가리킬 노드를 좌측 자식 노드로 한 것이다. 

#소스코드

최대힙 문제와 최소힙 문제는 부호만 반대이므로 최소힙에 대한 코드만 보면 다음과 같다.

#include<iostream>
 
using namespace std;
 
void pop();
void push(int num);
 
int arr[100005];//index 1부터 사용하니까
int n = 0;//힙에 들어있는 원소의 수
 
 
 
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
    int testnum = 0;
    int num = 0;
 
    cin >> testnum;
    for (int i = 0; i < testnum; i++) {
        cin >> num;
        if (num == 0) {
            pop();
        }
        if(num > 0){
            push(num);
        }
    }
 
}
 
void pop() {
    if (n == 0) {
        cout << 0 << "\n";
        return;
    }
    else {
        cout << arr[1] << "\n";
        arr[1] = arr[n];
        n--;
 
        //재정렬(index 1의 값이 변경됨)
        if (n != 0) {
            int t = 1;
            while (t*2 <= n) {
                if (t * 2 == n) {
                    if (arr[t * 2] < arr[t]) {
                        swap(arr[t * 2], arr[t]);
                        t *= 2;
                    }
                    else {
                        break;
                    }
                }
                else {
                    if (arr[t * 2] < arr[t * 2 + 1] && arr[t * 2] < arr[t]) {
                        swap(arr[t * 2], arr[t]);
                        t *= 2;
                    }
                    else if (arr[t * 2] >= arr[t * 2 + 1] && arr[t * 2 + 1] < arr[t]) {
                        swap(arr[t * 2 + 1], arr[t]);
                        t = t*2 +1;
                    }
                    else {
                        break;
                    }
                }
            }
        }
    }
}
 
void push(int num) {
    n++;
    arr[n] = num;
 
    //재정렬(index n의 값이 변경됨)
    int t = n;
    while (t != 1) {
        if (arr[t / 2] > arr[t]) {
            swap(arr[t / 2], arr[t]);
            t /= 2;
        }
        else {
            break;
        }
    }
}
 
 

 

참고) 힙의 개념: twpower.github.io/137-heap-implementation-in-cpp