자료 구조에서의 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;
}
컴퓨터 공학에서 Big-O 표기법은 알고리즘의 분류에 사용되는데, 입력의 크기가 변함에 따라 어떻게 반응하는지 나타낸다. 즉 입력에 따른 시간 복잡도 ( time complexity )를 나타낸다.
만약 알고리즘 A가 입력 N개에 대해서 (10N + 5) 연산 횟수를 가진다면, N 이 10이하의 작은 수라면, N에 곱해진 10이나, 더해진 5가 성능에 큰 영향을 주겠지만, N이 1010000 정도 되는 큰 수라면 10을 곱하거나, 5를 더하는 정도는 연산 시간에 큰 영향을 주지 못한다.
따라서 알고리즘 A를 Big-O 로 표기하면 O(N) 이된다.
마찬가지로, 알고리즘 B가 입력 N개에 대해 (10N2 + 88N + 38135)의 연산 한다고 가정하면 N 이 무한에 가깝게 클 수록 기울기를 정하는 요인은 N2 이 되므로 Big-O로 표기하면 O(N2 )이 된다.
클래스
아래는 알고리즘을 분석할 때 사용하는 일반적인 분류들이다.
성능은 위에서 아래로 갈 수록 안좋다.
O(1) - constant - 입력 개수에 상관없이 같은 시간이 걸린다. 예를 들면 배열에 인덱스로 접근.
O(logN) - logarithmic - 대략적으로 입력이 10배 증가할 때 소요 시간이 1정도 증가한다. 대표적인 예는 이진검색( binary search )
O(N) - linear - 입력 개수에 대해 선형적으로 증가. 즉 10개 입력시 1의 시간이 소요되면, 100개 입력 시 10의 시간이 소요. 일반적으로 for 루프를 이용해서 탐색을 하는 경우에 해당된다.
O(N logN) - superlinear - O(N) 보다는 소요시간 증가폭이 크지만, 충분히 유용한 알고리즘. 성능좋은 정렬(Sort) 알고리즘 들이 이 범주에 속한다. (MergeSort, QuickSort...)
O(N2) - quadratic - 입력 개수 제곱에 비례해서 증가. 대표적인 예는 BubbleSort. 프로그래밍시 for루프를 2개 중첩해서 사용한 경우.
O(NC) - polynomial - 문자 그대로 N이 증가함에 따라 특정 계수로 증가하는 경우.
O(CN) - exponential - 매우 빠르게 증가. 위의 O(NC)보다 증가폭이 더 크다.
O(N!) - factorial - 최악의 성능, N이 작은 경우에도 증가폭이 기하급수적으로 늘어난다.
계산법
일반적인 계산이 가능한 경우.
O(1), O(N), O(N2) 등은 일반적으로 계산이 가능하다.
- O(1) 은 입력의 크기에 관계없이 일정한 시간이 소요되는 알고리즘으로, 배열의 인덱스로의 접근은 배열의 크기에 상관없이 같은 시간이 소요된다.
int getValue( int index )
{
return array_[index];
}
- O(N) 은 정렬되지 않은 배열에서의 특정값 검색처럼 모든 원소를 순회해야 하는 경우이다
int findValue( int value )
{
for( int i = 0; i < ARRAY_MAX; ++i )
{
if( array_[i] == value )
return array_[i];
}
return 0;
}
위 함수는 평균적으로 1/2N, 최악의 경우 N 이지만, big O 로 표기하면 상수는 무시되므로O(N) 이 된다.
- O(N2) 은 for문을 중첩해서 사용하는 경우에 해당되며 대표적으로 BubbleSort가 있다.
void BubbleSort( int array[], int arraySize )
{
for( int i = 0; i < arraySize; ++i )
{
for( int j = 0; j < arraySize - 1; ++j )
{
if( array[j] > array[j+1] )
{
// swap
int tmp = array[j+1];
array[j+1] = array[j];
array[j] = tmp;
}
}
}
}
일반적이지 않은 경우는?
- O(logN) 과 O(N logN) 은 위에서 본 경우처럼 명확하게 계산하기 힘들다. 이해를 돕기 위해 실제 수치로 계산을 해보자.
N = 10 : log10 = 1 10log10 = 10
N = 20 : log20 = 1.3 20log20 = 26.02
N = 100 : log100 = 2 100log100 = 200
N = 1000 : log1000 = 3 1000log1000 = 3000
분명히 O(N logN)은 O(N) 보다는 그래프로 그렸을 때 기울기가 가파르다. 하지만 정렬알고리즘의 경우 O(N logN) 보다 뛰어날 수 없다는게 수학적으로 증명되었으니, 복잡도가 O(N logN)이라면 좋은 알고리즘에 속한다.
일반 전화번호부와 다르게 알파벳에 따른 인덱스가 없는 전화번호부에서 "John Smith"를 찾는다고 가정해보자. 일단 전화번호부의 가온데를 펴고 Smith의 "S"를 찾는다. 처음 연 페이지에 John Smith가 있을 수 있지만, 대부분의 경우 없을것이다. 그럼 그 페이지의 알파벳을 보고 다음 펼칠곳을 찾는다. 만약 펼친 페이지가 "I" 라면 S는 뒤에 있으니 그 뒤에서 똑같이 중간을 펼치고 알파벳을 비교 한다.
위 내용이 바로 이진검색 ( binary search ) 이다. 페이지가 1,000,000 페이지라면 최대 20번만 페이지를 찾는 다면 반드시 원하는 페이지를 찾을 수 있다.( 220 = 1048576 )
Big-O로 표현하면 O(logN)이 된다. logarithmic complexity 에서 로그의 밑은 중요하지 않다. ln이든, log2N, log10N 이든, Big-O로 표현하면 모두 logN이 된다.
반대로, 전화번호를 가지고 이름을 찾는다고 가정해 보자. 전화번호부는 이름으로 정렬된 데이터이기 때문에 일치하는 전화번호를 찾기 위해서는 처음부터 마지막까지 모든 번호를 비교해서 검색해야 한다. 페이지가 1,000,000 페이지 전화번호부라면 1번에 전화번호가 있을 확률도 있지만 1,000,000번째 전화번호가 있을 확률도 같다. 확률로 나타내면 1/2N이 되겠지만, Big-O로 표현하면 O(1/2N) 은 O(N)이 되므로, 복잡도는 O(N)이 된다.
Binary search tree (BST)는 Tree의 특별한 경우로 아래의 몇가지 항목을 만족시킨다.
- 왼쪽 서브트리 ( left subtree )는 현재 노드의 값 보다 작은 노드들만 위치한다.
- 오른쪽 서브트리 ( right subtree ) 는 현재 노드의 값 보다 큰 노드들만 위치한다.
- 왼쪽, 오른쪽 서브 트리 모두 각각 binary search tree이다.
- 모든 노드는 최대 2개의 자손( successor )를 가질 수 있다.
- 중복되는 값을 가진 노드는 없어야 한다.
- 모든 노드는 root로 부터 고유한 길( unique path )이 있다.
Binary Tree 와 Binary search tree의 차이점.
Binary search tree (BST)는 Binary Tree의 특이한 케이스이다. Binary Tree는 노드가 2개의 자식 노드를 가질 수 있는데, BST는 그 자식 노드가 왼쪽에는 자신보다 작은값을, 오른쪽에는 자신보다 큰 값을 갖는 경우를 말한다.
BST의 특이점
Binary "SEARCH" tree라는 이름에서 알 수 있듯, root 및 모든 subtree를 기준으로 특정 값을 찾을 때 찾는 값이 해당 노드값 보다 작으면 왼쪽 subtree를 크다면 오른쪽 subtree를 검색하면 원하는 값을 O(logN)이 런타임으로 찾을 수 있다.
트리를 InOrder방식으로 방문하면, 오름 차순으로 정렬된 데이터를 얻을 수 있다.
BST with C++
BST에 사용될 메서드를 생각해보자.
1. 값을 추가하는 add() 메서드
2. 값을 제거하는 remove() 메서드
3. 값이 존재하는지 찾는 find()메서드
값을 추가하는 add() 메서드
외부에서 호출하는 addData() 함수를 하나 만들고, 내부적으로 재귀적으로 사용할 _addData() 함수를 만들어서 밖에서는 안보이도록 숨기자. addData() 에서는 추가할 값만 받고, _addData() 함수에서는 부모 노드 값을 받아서 적당한 위치를 찾아 데이터를 만들자.
bool Tree::addData( int value )
{
return _addData( root_, value );
}
외부에서 보이는 addData() 메서드이다. 전달인자는 추가할 값 하나.
bool Tree::_addData( Node*& node, int value )
{
if( node == NULL )
{
node = new Node;
if( node == NULL )
return false;
node->data_ = value;
node->left_ = node->right_ = NULL;
return true;
}
else
{
if( node->data_ > value )
{
return _addData( node->left_, value );
}
else if( node->data_ < value )
{
return _addData( node->right_, value );
}
}
return false;
}
내부적으로 사용하는 _addData() 메서드이다. 추가할 노드의 부모 노드의 참조를 전달인자로 받는다. 만약 Node*& 연산이 가독성이 떨어진다고 생각되면 typedef를 이용해 예쁘게 만들어도 된다. _addData()에 node가 NULL인 경우는 원하는 위치를 찾은 경우이다. 메모리를 할당하고 값을 세팅하자.
넘겨받는 node가 NULL이 아닐 경우 자리를 찾기 위해 값 비교를 한다. 만약 value값이 작다면 node의 left_를, 크다면 right_를 전달인자로 _addData()를 recursive 호출 하자. 그럼 적당한 자리를 찾아가서 값이 추가가 된다.
이런식으로 add된 값들은 balance되지 않는다. 따라서 10, 9, 8, 7 이런식으로 add를 하면 10을 루트로 가진 왼쪽노드로만 이루어진 트리가 만들어진다. AVL트리는 나중에 따로 연구하자.
값을 제거하는 remove()메서드
상대적으로 remove 메서드는 add보다 조금 복잡하다. leaf를 remove하면 간단하지만, 중간에 값을 remove하면 트리를 새로 구성해야 하기 때문이다.
remove하는 시나리오는 크게 3개이다.
- leaf를 remove하는 경우 : 그냥 삭제하자
- left에 subtree가 있는 경우 : left의 subtree에서 가장 큰 값을 가져와 현재 node에 대입하고, 그 노드를 제거
- right에 subtree가 있는 경우 : right의 subtree에서 가장 작은 값을 가져와 현재 node에 대입하고, 그 노드는 제거
- remove를 재귀적으로 호출하도록 하자.
bool Tree::removeData( int value )
{
Node** node = _findNode( value );
if( node == NULL )
return false;
return _removeData( *node );
}
내부적으로 호출되는 _removeData() 메서드이다. 일단 제거될 node가 leaf인지 확인하자. 이 노드는 그냥 제거하면 된다. leaf가 아니라면 머리를 써야된다. left나 right중 아무 노드나 골라서 먼저 찾아보자. 이 자리에는 left노드 중 가장 큰 값이나, right 노드 중 가장 작은 값이 오면 BST의 조건을 만족한다.
코드에서는 right먼저 검사를 했다. right에서 가장 작은 값을 찾자. BST특성 상 작은 값은 left에 존재하므로 left만 따라가면 된다. 만약 left가 NULL이라면 이 값이 가장 작은 값이다. 그럼 그 값을 복사해서 내 자리에 놓고 그 자리는 제거한다. 그럼 재귀적으로 제거된 값에 대해서 똑같은 연산이 반복되서 트리가 구성된다.
값을 찾는 find() 메서드
BST의 특징을 따라 노드를 따가라면 된다. 현재 노드와 비교해서 값이 작으면 left로, 반대로 크다면 right로 이동해서 똑같이 비교를 하면 된다.
