Heap

자료 구조에서의 Heap은 Heap property를 만족하는 특별한 트리이다. Dynamic memory allocation의 heap과 다르니 혼동하지 않아야 한다.

Heap property
 - 부모 노드와 자식노드는 Heap 전체에 적용된 순서에 따라 정렬된다.
 - 만약 부모 노드가 자식노드의 키값보다 항상 크거나 같다면 최대힙(max heap)이라 한다.
 - 반대로 부모노드가 자식노드의 키값보다 항상 작거나 같아면 최소힙(min heap)이라고 한다.
- 따라서 max heap에서 root는 그 트리의 최대값이, min heap에서의 root는 그 트리의 최소값이 된다.
- 일반적으로 heap은 complete binary tree로 구현된다.

Heap의 구현

Heap은 complete binary tree특징이 있으므로 주로 배열을 이용해서 구현을 한다.

해당 노드(인덱스) "i"가 주어졌을 때 부모 노드와 자식노드를 구하는 방법은 아래와 같다.

indexParent = floor( (i-1) / 2 )

indexLeft = (2*i) + 1;

indexRight = (2*i) + 2;

이제 위 공식을 이용해 클래스를 만들어보자. 원래 자료 관리에 제한이 없게 dynamic memory를 써야 하지만, 알고리즘을 파악하는게 먼저니 배열을 미리 잡아놓자.

#define HEAP_SIZE 100
class Heap
{
private:
    int elements_[HEAP_SIZE];
    int elementIndex_;

public:
    Heap()
    {
        memset( elements_, 0, sizeof( elements_) );
        elementIndex_ = 0;
    }

    bool addData( int value );
};

* Add

데이터를 저장할 배열을 하나 생성하고, 마지막 인덱스를 저장할 값도 하나 생성하자. 이 인덱스가 힙의 크기가 된다. 일단 사용할 메서드는 값을 넣는 addData() 메서드이다.

bool Heap::addData( int value )
{
    if( elementIndex_ == 0 )
    {
        elements_[elementIndex_++] = value;
        return true;
    }

    if( elementIndex_ == HEAP_SIZE )
    {
        return false;
    }

    int index = elementIndex_;
    elements_[index] = value;

    do
    {
        int iParent = static_cast<int>(floor(index-1) / 2));
        if( elements_[iParent] < elements_[index] )
        {
            // swap
            int tmp = elements_[iParent];
            elements_[iParent] = elements_[index];
            elements_[index] = tmp;
        }
        else
        {
            break;
        }

        index = iParent;
    }while( index > 0 );

    ++elementIndex_;
    return true;
}

값을 넣을 때 일단 힙의 인덱스를 체크하자. 0이라면 빈 힙이므로 그냥 값을 넣자. 만약 인덱스가 최대 값이면 배열이 다 찬 상태이므로 에러처리를 하자.

이제 맨 배열의 맨 마지막 자리에 전달받는 값을 대입하고 부모인덱스와 비교를 하자. 위에 함수에서는 클 경우 swap이 발생하므로 최대힙이 만들어진다. 만약 부모인덱스와 비교해서 크지 않다면 더 처리할 필요는 없다. 맨 마지막으로 값이 하나 늘었으니 힙인덱스를 하나 늘려주자.

위 연산은 데이터의 길이가 증가해도 자신의 부모 노드와 값을 비교해서 swap하므로 O(logN) 시간복잡도를 갖는다.

* Pop

힙에서 데이터를 삭제하는 경우는 선택해서 삭제 할 수도 있지만 일반적으로 맨 위의 값을 꺼내오는 경우이다.

complete balance tree 특성 상 현재 노드에서 right child에만 값이 있는 경우는 없으므로 left child가 최대 인댁스를 넘었으면 그 노드가 leaf인 경우이고, left는 넘지 않았는데 right만 넘었으면 left가 leaf가 된다. 그래서 현재 노드에서 child와 비교 후 max heap일 경우 두 child 중 큰 값과 swap하고, min heap일 경우 두 child중 작은 값과 swap하면 된다.

void Heap::_swap( int index1, int index2 )
{
    int temp = elements_[index1];
    elements_[index1] = elements_[index2];
    elements_[index2] = temp;
}

int Heap::popData()
{
    if( elementIndex_ == 0 )
        return 0;
 
    int head = elements_[0];
    elements_[0] = elements_[--elementIndex_];

    int currentIndex = 0; 

    for(;;)
    {
        int left = (2*currentIndex) + 1;
        int right = (2*currentIndex) + 2;

        if( left >= elementIndex_ )
        {
            // balance 트리이기 때문에 left가 범위를 벗어났으면 더 비교할 필요가 없다
            break;
        }
        else if( right >= elementIndex_ )
        {
            // left가 범위를 벗어나지 않았는데 right가 범위를 벗어난 경우는 left만 남은 경우이므로 left만 비교하자.
            if( elements_[currentIndex] < elements_[left] )
            {
                _swap( currentIndex, left );
            }
            break;
        }
        else
        {
            // 두 자식 모두 비교해서 다음 인덱스를 세팅하자.
            int selectedIndex = elements_[left] > elements_[right] ? left : right;
            _swap( currentIndex, selectedIndex );
            currentIndex = selectedIndex;
        }
    }

    return head;
}

출처
http://en.wikipedia.org/wiki/Binary_heap