(Data Structure) 최소 힙(Minimum Heap)

06 Mar 2018

Reading time ~2 minutes

최소 힙이란?

부모 노드가 자식 노드보다 항상 작은 트리 구조를 말한다.
완전 이진 트리이고, 배열로 구현된다. 배열로 구현된다는 말은, 부모 노드의 index가 parentIndex라고 하면 왼쪽 자식 노드의 인덱스는 parentIndex*2, 오른쪽 자식 노드의 인덱스는 parentIndex*2+1 이라는 의미이다.

삽입

최고 깊이에서 가장 오른쪽에 삽입된다. 새로 삽입된 노드의 부모 노드를 계속 bottom-up 하면서, 부모 노드가 자신보다 더 클 경우 부모 노드와 자신 노드를 swap한다.

최소 값 꺼내기

최소 값(루트 노드)을 꺼낸다음, 트리의 가장 루트 노드를 가장 마지막으로 삽입된 값(최고 깊이에서 가장 오른쪽 노드)로 대체한다. 그 다음, 힙정렬의 성질을 유지하기 위해 루트 노드에서 부터 자식 노드들을 top-down 하며 자신보다 더 작은 자식 노드가 있으면 자신과 자식노드를 swap한다. 만약 왼쪽 자식과 오른쪽 자식이 둘 다 자신보다 작다면, 둘 중에 더 작은 자식과 swap 해야한다.

코드

가장 루트 노드의 인덱스를 1로 설정하는게 코드가 훨씬 더 깔끔하고 복잡하지 않다.

#include <iostream>

using namespace std;

class MinHeap
{
private:
    int* tree;
    int capacity;
    int size;
public:
    MinHeap(int capacity) : capacity(capacity), size(0)
    {
        tree = new int[capacity];
    }
    ~MinHeap()
    {
        delete []tree;
    }

    // 배열의 크기를 확장한다.
    void extend()
    {
        int* tmp = new int[size];

        for(int i=0;i<size;i++)
            tmp[i] = tree[i];

        capacity *= 2;
        tree = new int[capacity];

        for(int i=0;i<size;i++)
            tree[i] = tmp[i];
    }

    void insert(int value)
    {
        size++;

        int childPos = size;
        int parentPos = childPos/2;

        if(size >= capacity)
            extend();

        tree[childPos] = value;

        while(parentPos > 1 && tree[childPos] < tree[parentPos])
        {
            swap(tree[childPos], tree[parentPos]);

            childPos = parentPos;
            parentPos = childPos/2;
        }
    }

    int extractMin()
    {
        int min = tree[1];

        // 최소값 노드를 가장 마지막 요소로 대체한다.
        tree[1] = tree[size];
        tree[size] = 0;

        size--;
        // 힙 트리를 유지한다.
        int parentPos = 1;
        int leftPos = parentPos*2;
        int rightPos = parentPos*2 + 1;

        // 왼쪽 자식이 있을 경우에만 균형 맞추기를 한다.
        // 왼쪽 자식이 없으면 오른쪽 자식도 없기 때문이다.(힙은 완전 이진 트리)
        while(leftPos <= size)
        {
            int targetPos;

            if(rightPos > size) // 오른쪽 자식이 없는 경우
            {
                if(tree[parentPos] < tree[leftPos])
                    break;
                else
                    targetPos = leftPos; //왼쪽 자식 선택
            }
            else //양쪽 자식 다 있는 경우
            {
                //이미 자식이 둘 다 커버리면 균형 맞추기를 종료한다.
                if(tree[parentPos] < tree[leftPos] && tree[parentPos] < tree[rightPos])
                    break;
                else
                    targetPos = (tree[leftPos] < tree[rightPos]) ? leftPos : rightPos; // 양쪽 자식 중에 더 큰 녀석과 부모와 교환한다.
            }

            swap(tree[targetPos], tree[parentPos]);

            // 부모 위치와 자식 위치를 새로 갱신한다.
            parentPos = targetPos;

            leftPos = targetPos*2;
            rightPos = targetPos*2 + 1;
        }

        return min;
    }
    void printAll()
    {
        for(int i=1;i<=size;i++)
            cout<<tree[i]<<" ";
        cout<<endl;
    }
};
int main()
{
    MinHeap mh(10);

    mh.insert(1);
    mh.insert(7);
    mh.insert(10);
    mh.insert(9);
    mh.insert(5);
    mh.insert(6);

    mh.printAll();

    cout<<mh.extractMin()<<endl;
    cout<<mh.extractMin()<<endl;
    cout<<mh.extractMin()<<endl;
    cout<<mh.extractMin()<<endl;
    cout<<mh.extractMin()<<endl;
    cout<<mh.extractMin()<<endl;
}

data structure