힙이란?
힙은 특정 규칙을 만족하는 이진 트리이다.
힙의 종류엔 최대힙, 최소힙이 있으며 최대 원소를 찾는가, 최소 원소를 찾는가의 차이가 있다.
최대힙을 중점적으로 설명하자면 부모 노드는 항상 자식노드보다 커야한다. 그러므로 루트는 가장 큰 최대 원소가 되어야한다.
힙은 단순 이진 트리가 아닌 아래의 두 가지 조건을 만족하는 트리이다.
-
마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
-
마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.
힙은 보통 배열을 이용해 구현한다.
힙의 조건이 매우 엄격하기 때문에 구현에는 용이하다.
힙은 항상 다음 조건을 만족하게 된다.
-
A[i]의 왼쪽 자손은 A[i*2 + 1] 이다.
-
A[i]의 오른쪽 자손은 A[i*2 + 2]이다.
-
A[i]의 부모 노드는 A[(i-1) / 2]이다. (나눗셈 결과를 내림할 것)
새 원소의 삽입
원소의 삽입을 하는 법은 우선 1번 조건을 만족시키기 위해 트리의 가장 끝에 원소를 우선 추가하는 것이다.
그 후 2번 조건을 만족하기 위해 부모 노드와 새로 추가한 노드를 비교한 후 크기가 더 크다면 swap 한다. 이를 루트까지 계속 비교한다.
이렇게 삽입하면 힙의 두가지 조건을 모두 만족하게 된다. 코드를 보면 이해가 될 것이다.
void push_heap(int value)
{
Heap.push_back(value);
int idx = Heap.size() - 1;
while (idx > 0 && Heap[idx] > Heap[(idx - 1) / 2]) {
swap(Heap[idx], Heap[(idx - 1) / 2]);
idx = (idx - 1) / 2;
}
}
최대 원소의 삭제
힙의 최대 원소를 확인하는 법은 그냥 0번째 값을 읽으면 된다.
그렇다면 삭제는 어떻게 해야할까. 트리의 루트에 제일 오른쪽 단말 노드 값을 넣는 것이다.
그 후 루트와 자식을 비교하면서 더 큰 자식을 루트에 넣는다. 역시 코드를 보면 이해가 될 것이다.
void pop_heap() {
Heap[0] = Heap.back();
Heap.pop_back();
int here = 0;
while (true) {
int left = here * 2 + 1, right = here * 2 + 2;
if (left >= Heap.size()) break;
int next = here;
if (Heap[next] < Heap[left])
next = left;
if (right < Heap.size() && Heap[next] < Heap[right])
next = right;
if (next == here) break;
swap(Heap[here], Heap[next]);
here = next;
}
}