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
