dev-miri
2-2 힙 본문
힙은 다음과 같은 시간 복잡도를 만족해야 한다.
- O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 함
- O(log N) : 원소 삽입에 대한 시간 복잡도
- O(log N) : 최대 원소 삭제에 대한 시간 복잡도
원소 삽입 혹은 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.
다만 이 경우에는 완전 이진 트리(complete binary tree)를 사용해야 한다.
완전 이진 트리는
- 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 있고
- 마지막 레벨에서는 왼쪽부터 차례대로 노드가 있는 트리이다.
완전 이진 트리는 새로운 원소를 트리의 마지막 레벨에 추가하는 방식으로 구성할 수 있다.
만약 마지막 레벨의 모든 노드가 채워져 있다면 새로운 레벨을 하나 더 만들고, 맨 왼쪽 위치에 노드를 추가한다.
완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다.
즉, 루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다.
이러한 방식의 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없기 때문에 메모리 사용 측면에서 효율적이다.
부모 노드로부터 자식 노드로 이동하는 것은 단순히 배열의 인덱스 계산으로 가능하다.
만약 부모 노드가 i번째 배열 원소로 저장되어 있다면 자식노드는 2*i + 1 또는 2*i +2 번째 인덱스로 접근하면 된다.
마찬가지로 자식 노드가 i번째 인덱스라면 부모 노드는 (i-1)/2 번째 인덱스다.
이제 원소를 삽입하거나 삭제할 때 유지해야 할 힙의 불변성 또는 조건에 대해 알아보자.
첫 번째 조건은 최대 원소에 즉각적으로 접근 가능해야 한다는 점이다. 이를 위해 최대 원소가 항상 고정된 위치에 있어야 한다.
힙을 구현할 때는 항상 최대 원소가 트리의 루트에 있도록 설정한다. 이를 위해 부모 노드가 두 자식 노드보다 항상 커야 한다는 불변성을 유지하도록 설정해야 한다. 이렇게 구성한 힙을 최대 힙(max heap)이라고 한다.
최대 원소에 빠르게 접근할 수 있다면 반대로 최소 원소에 빠르게 접근할 수 있도록 힙을 구성할 수도 있다.
이러한 힙을 만들려면 앞서 설명했던 모든 비교 연산을 반대로 설정하면 된다. 이렇게 만들어진 힙을 최소 힙(min heap)이라고 한다.
힙 연산
힙에 원소 삽입하기
힙의 가장 중요한 불변성은 완전 이진 트리를 유지해야 한다는 점이다.
완전 이진 트리를 유지하고 있어야 배열 자료 구조를 이용하여 힙을 저장할 수 있다.
완전 이진 트리를 유지하는 힙에 새 원소를 삽입하려면 단순히 배열의 맨 마지막 위치에 원소를 추가하면 된다.
이 작업은 기존 트리의 마지막 레벨, 마지막 노드 바로 오른쪽에 새로운 노드를 추가하는 것과 같다.
이번에는 다른 불변 조건에 대해 생각해보자. 모든 노드는 자식 노드보다 더 큰 값을 가지고 있어야 한다.
일단 기존의 트리는 이미 이 불변 조건을 만족하고 있다고 가정하자.
그러나 새로운 원소를 트리의 맨 마지막에 추가한 후에는 이 조건이 성립되지 않을 가능성이 생긴다.
이를 해결하기 위해 새로 삽입한 원소의 부모 노드와 값을 비교하고, 만약 부모 노드가 더 작으면 서로 교환(swap)한다.
만약 부모 노드에 다른 자식 노드가 있다 하더라도 이 자식 노드는 새로 추가한 원소보다 작다(새 원소 > 부모 노드 > 다른 자식 노드)
그러므로 새로 추가한 원소를 루트 노드로 간주하는 서브 트리는 힙 불변성을 만족하게 된다.
그러나 새 원소가 여전히 새 부모 노드보다 큰 값을 가질 수 있다. 따라서 전체 트리에서 불변 조건이 만족하도록 교환 작업을 반복해야 한다.
완전 이진 트리의 높이는 최대 log N이므로, 삽입 연산의 시간 복잡도는 O(log N)으로 표현할 수 있다.
힙에서 원소 삭제하기
힙에서는 가장 큰 원소만 삭제할 수 있다. 다른 원소에는 직접 접근할 수 없기 때문이다.
최대 원소는 항상 트리의 루트에 존재하므로, 루트 노드를 삭제해야 한다.
루트를 삭제할 경우, 어느 노드를 이용하여 루트를 대체할 것인지를 결정해야 한다.
이를 위해 먼저 루트 노드와 트리의 맨 마지막 노드를 서로 교환한 후, 마지막 노드를 삭제한다.
이렇게 하면 최대 원소를 삭제한 것이 되며, 다만 루트 위치에서 부모 노드가 자식 노드보다 커야 한다는 불변성은 만족하기 못하게 된다.
이 문제를 해결하기 위해 루트 노드와 두 자식 노드를 서로 비교하여 그중 더 큰 노드와 서로 교환한다.
이제 루트 노드의 두 서브 트리 중 하나에 대해 불변 규칙이 깨진 상태가 되었을 것이다. 그러므로 서브 트리에 대해서도 노드 교환 작업을 재귀적으로 반복한다. 이러한 방식으로 불변성을 만족하지 못하는 위치가 점차 트리 아래쪽으로 이동하게 된다.
교환 작업의 최대 횟수는 트리의 높이와 같으므로 원소 삭제의 시간 복잡도는 O(logN) 으로 표현할 수 있다.
힙 초기화하기
벡터, 리스트, 덱과는 달리 힙은 불변성을 유지해야 하기 때문에 초기화가 간단하지 않다.
가장 간단한 해결책은 비어 있는 힙에 하나씩 원소를 삽입하는 것이다.
그러나 이 작업은 O(Nlog N)의 시간 복잡도를 가지며 효율적이지 않다.
힙 생성 알고리즘(heapification algorithm)을 사용하면 O(N) 시간에 힙을 초기화할 수 있다.
이 알고리즘의 기본 개념은 매우 간단하다.
전체 트리의 아래쪽 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트 하는 방식이다.
일단 맨 마지막 레벨은 자식 노드가 없으므로 이미 힙 속성을 만족한다고 간주하자. 그리고 한 레벨씩 트리 위로 올라가면서 힙 속성을 만족하도록 트리를 업데이트한다. 이 작업은 O(N)의 시간 복잡도를 갖는다.
C++ 표준은 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 std::make_heap() 함수를 제공한다.
Exercise Problem : 중앙값 구하기
어떤 소스로부터 한 번에 하나의 데이터를 연속적으로 받는다고 가정하자.
그리고 매번 데이터를 받을 때마다 지금까지 받은 데이터의 중앙값(median)을 계산해야 한다고 가정하자.
간단한 방법은 매번 데이터를 받을 때마다 모든 데이터를 정렬하고, 그 중 가운데 원소를 반환하는 것이다.
그러나 이러한 작업은 정렬 연산 때문에 O(Nlog N)의 시간 복잡도를 갖는다.
들어오는 데이터양이 늘어날수록 이 방식은 매우 많은 리소스를 사용하게 된다.
여기서는 힙을 이용하여 최적화하는 방법을 알아보자.
#include <iostream>
#include <queue>
#include <vector>
//두 개의 힙을 이용하여 데이터를 저장
//새로 들어오는 데이터가 기존 데이터의 중앙값보다 작으면 최대 힙에 저장하고, 크면 최소 힙에 저장
//이런 방식을 사용하면 두 힙의 최상단 원소를 이용하여 중앙값을 계산할 수 있게 된다
struct median
{
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
void insert(int data)
{
if(maxHeap.size()==0)
{
maxHeap.push(data);
return;
}
if(maxHeap.size() == minHeap.size())
{
if(data <= get())
maxHeap.push(data);
else
minHeap.push(date);
return;
}
if(maxHeap.size() < minHeap.size())
{
if(data > get())
{
maxHeap.push(minHeap.top());
minHeap.pop();
minHeap.push(data);
}
else
maxHeap.push(data);
return;
}
if(data < get())
{
minHeap.push(maxHeap.top());
maxHeap.pop();
maxHeap.push(data);
}
else
minHeap.push(data);
}
//지정된 원소로부터 중앙값을 구하여 반환하는 get() 함수
double get()
{
if(maxHeap.size() == minHeap.size())
return (maxHeap.top()+minHeap.top()) / 2.0;
if(maxHeap.size() < minHeap.size())
return minHeap.top()
return maxHeap.top();
}
};