C++로 Heap 구현하기

Heap은 완전 이진 트리의 일종으로 불완전 정렬 상태를 이루고 있다.

• Max Heap의 경우에는 부모 노드 >= 자식 노드
• Min Heap의 경우에는 부모 노드 <= 자식 노드

일반적으로 Priorty Queue를 구현하는데 사용한다. Heap 자료구조의 기본적인 알고리즘은 다음과 같다.

• 삽입
  가장 마지막 노드에 값을 삽입한다. 그리고 반복적으로 삽입한 노드의 부모 노드와 비교를 통해 Swap 연산을 한다.
• 삭제(최댓값 또는 최솟값 꺼내기)
  가장 위에 있는 노드(root)를 꺼낸다. 이 노드의 값이 최대 혹은 최소다. 가장 마지막 노드를 root 노드의 자리로 옮긴다. 반복적으로 자식노드와 비교를 통해 Swap 연산을 한다.
  

구현

#include <stdio.h>
#include <stdlib.h>

#define MAX_HEAP_SIZE 10

struct Heap {
    int size = 0;
    int heap[MAX_HEAP_SIZE];

    int push(int value) {
        if(size == MAX_HEAP_SIZE) return -1;

        heap[size] = value;
        update(size);
        size++;
    }

    int pop() {
        if(size == 0) return -1;

        int res = heap[0];
        heap[0] = heap[--size];
        downdate(0);

        return res;
    }

    void update(int idx) {
        int c = idx;
        int p = (c - 1) / 2;

        while(c > 0 && heap[c] > heap[p]) {
            swap(c, p);
            c = p;
            p = (c - 1) / 2;
        }
    }

    void downdate(int idx) {
        int p = idx;
        int c = 1;

        while(c <= size) {
            if(c < size && heap[c] < heap[c + 1]) c++;
            if(heap[c] <= heap[p]) break;

            swap(c, p);
            p = c;
            c = c * 2 + 1;
        }
    }

    int getSize() {
        return size;
    }

    void swap(int a, int b) {
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
    }
};

int main() {
    Heap* myHeap = new Heap();

    for(int i = 0 ; i < MAX_HEAP_SIZE ; ++i) {
        int value = rand() % 100;
        myHeap->push(value);
    }

    for(int i = 0 ; i < MAX_HEAP_SIZE ; ++i) {
        printf("%d번째 pop()의 결과는 %d\n", i, myHeap->pop());
    }
}