99클럽 코테스터디 10일차 TIL 최대 힙

최대 힙

• 문제 링크

문제 설명

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

    1. 배열에 자연수 x를 넣는다.
    2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

• 어제 풀이한 최소 힙과 비슷한 문제

문제 풀이

• 어제의 코드에서 push, pop 과정의 - 만 제거하면 풀리는 문제지만 그냥 하면 재미없을 것 같아서 직접 구현해보기로 했다.
• 배열에 넣어두고 구현하는 방식으로 했다.
  • 일반적인 트리구조에서는 배열을 사용할 때 문제가 발생할 수 있지만, Heap 은 완전이진트리의 구조를 띄기때문에 가능하다.

기본 설정

• 문제에서 최대로 연산 횟수가 100,000 회 이기 때문에 배열의 길이를 임시로 100,005 로 잡아줬다.
• heap 배열을 MAX 크기로 잡아주고, heapCnt로 push 할 때, 어떤 위치에 넣어야 하는 지 확인한다.

#define MAX 1000005

int heap[MAX];
int heapCnt = 0;

swap()

• heap 자료구조에서는 데이터를 삽입할때, 빼낼때 스왑이 빈번히 일어나므로 함수로 만들어서 따로 빼준다.

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

push(int number)

• heap 자료형에 데이터를 삽입하는 함수.
• 현재 보고 있는 곳 +1 한 곳에 데이터를 넣어주고 정렬해준다.
• 힙은 depth가 가장 낮은곳에 일단 데이터를 넣어두고 루트와 값을 비교해나가면서 정렬한다.

void push(int num) {
    heap[++heapCnt] = num;

    int chd = heapCnt;
    int par = chd/2;

    while (chd > 1 && heap[chd] > heap[par]) {
        swap(&heap[chd], &heap[par]);
        chd = par;
        par = chd/2;
    }
}

pop()

• 가장 최상단에 있는(루트에 있는) 데이터를 꺼내는 함수.
• top에 있는 숫자를 저장해주고 가장 작은 숫자(가장 낮은 곳에 있는) 숫자와 교환 해준뒤, heapCnt 를 하나 낮춰 배열의 전체 길이를 조절해 제거한 것 처럼 보이게 해준다.
• 루트를 기준으로 정렬해나간다.

int pop() {
    int res = heap[1];
    swap(&heap[1], &heap[heapCnt]);
    heapCnt -= 1;

    int par = 1;
    int chd = par*2;

    if (chd + 1 <= heapCnt) {
        chd = (heap[chd] > heap[chd+1]) ? chd : chd+1;
    }

    while (chd <= heapCnt && heap[chd]>heap[par]) {
        swap(&heap[chd], &heap[par]);
        par = chd;
        chd = par*2;

        if (chd + 1 <= heapCnt) {
            chd = (heap[chd]>heap[chd+1]) ? chd : chd+1;
        }
    }

    return res;
}

전체 코드

#include <bits/stdc++.h>
#define MAX 1000005

using namespace std;

int heap[MAX];
int heapCnt = 0;

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void push(int num) {
    heap[++heapCnt] = num;

    int chd = heapCnt;
    int par = chd/2;

    while (chd > 1 && heap[chd] > heap[par]) {
        swap(&heap[chd], &heap[par]);
        chd = par;
        par = chd/2;
    }
}

int pop() {
    int res = heap[1];
    swap(&heap[1], &heap[heapCnt]);
    heapCnt -= 1;

    int par = 1;
    int chd = par*2;

    if (chd + 1 <= heapCnt) {
        chd = (heap[chd] > heap[chd+1]) ? chd : chd+1;
    }

    while (chd <= heapCnt && heap[chd]>heap[par]) {
        swap(&heap[chd], &heap[par]);
        par = chd;
        chd = par*2;

        if (chd + 1 <= heapCnt) {
            chd = (heap[chd]>heap[chd+1]) ? chd : chd+1;
        }
    }

    return res;
}

int main () {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int N;
    cin >> N;

    for (int i=0; i<N; i++) {
        int tmp;
        cin >> tmp;
        if (tmp == 0) {
            if (heapCnt == 0) cout << 0 << "\n";
            else {
                int num = pop();
                cout << num << "\n";
            }
        } else {
            push(tmp);
        }
    }

}

회고

• heap의 구조가 어떻게 되어있는지 알 수 있는 기회였다. SSAFY에서 공부할 때는 그냥 사용하기에 급급했는데, 원리를 아니까 확실히 이해가 잘 되는 느낌이다.
• 자료가 많아서 구현하기 편했다.

참고자료

[자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙
[자료구조] 힙(heap)이란
Heap(data structure)
[알고리즘/C, C++] 최대 힙 구현하기
[Algorithm] C/C++에서 힙(Heap) 구현하기