Heap

개요

노드에 키를 저장하는 이진트리로, 다음 두 가지 성질을 만족한다.

 

• Heap order: 루트를 제외한 모든 노드 v에 대해 key(n) ≥ key( parent(n) )
• Complete binary tree: 깊이 i [0 : h)에 노드 총 2ⁱ개. 특히 i = h-1에서 internal nodes are to the left of the external nodes 라고 하는데 잘 모르겠다.

 

Last node

최대 깊이 h에서 가장 오른쪽에 있는 노드

 

 

트리의 높이

O(log n) 이다.

 

깊이 i [0 : h)에 2ⁱ개의 노드가 있고, h에 최소 한 개의 노드가 있다.

 

식으로 쓰면 n ≥ 1 + 2 + ... + 2^h-1 + 1 = 2^h 이다. 즉 n ≥ 2^h 이다.

 

양변에 로그를 취하면 log n ≥ 2^h 이다.

 

 

힙과 우선순위 큐

힙의 노드에 (key, elem) 쌍을 저장하고, Last node의 위치를 track 하여 우선순위 큐를 구현할 수 있다.

 

 

삽입 (우선순위 큐의 insert)

새 Last node의 position Z를 찾는다.

 

Z에 키 k를 삽입한다.

 

Upheap으로 Heap order를 복구한다.

 

 

Upheap

삽입한 노드 (Insertion node)로부터 올라가며 k와 부모를 swap한다.

 

k보다 부모노드의 키가 작거나 k가 루트가 되면 Upheap을 마친다.

 

트리의 높이가 O(log n) 이므로 O(log n)번의 시행에 마칠 수 있다.

 

 

삭제 (우선순위 큐의 removeMin)

힙의 루트를 삭제하고, Last node의 position Z에 있는 키로 교체한다.

 

Z를 삭제한다.

 

Downheap으로 Heap order를 복구한다.

 

 

Downheap

루트로부터 내려가며 k를 자식 중 더 작은 키를 가진 자식과 swap한다.

 

k보다 자식노드의 키가 크거나 k가 리프노드가 되면 Downheap을 마친다.

 

트리의 높이가 O(log n) 이므로 O(log n)번의 시행에 마칠 수 있다.

 

 

Heap sort

Heap 기반 우선순위 큐에 원소 n개를 넣었을 때 다음과 같은 효율을 기대할 수 있다.

 

공간복잡도 O(n)

 

삽입 및 삭제 O(log n)

 

size, empty, min O(1)

 

정렬 O(n log n)

 

 

배열기반 힙 구현

키가 n개인 힙을 만들자.

 

크기 n+1의 배열 A를 사용하며, A[0]는 사용하지 않는다.

 

A[i]의 왼쪽 자식은 A[2*i], 오른쪽 자식은 A[2*i + 1]임을 암시적으로 알 수 있다.

 

삽입은 A[n+1], 삭제는 A[n]에서 한다.

 

In-place Heap sort가 가능하다.

 

 

In-place Heap sort

3	7	2	1	4
3	7	2	1	4
2	3	7	1	4
1	2	3	7	4
1	2	3	4	7

 

밝은 영역이 힙, 어두운 영역이 Array이다.

 

 

두 힙 Merge

키 k와 두 힙이 주어지면, k를 가지는 루트 노드에 두 힙을 서브트리로 연결하여 병합한다.

 

물론 그 다음 Downheap을 한다.

 

 

Bottom-up Heap construction

i번째 단계에, 각각 2ⁱ-1개의 키를 가지는 힙 쌍을 2ⁱ⁺¹-1개의 키를 가지는 하나의 힙으로 병합한다.

 

O(log n) 번의 시행으로 마칠 수 있다.

 

최악의 경우, Downheap으로 각 노드를 최대 두 번 방문한다.

 

이러한 Downheap 경로 중 하나는 오른쪽 이후 계속 왼쪽으로 나아가는 경로가 있다.

 

하지만 결국 O(n) 개의 노드를 방문하는 것으로, O(n)의 수행시간에 힙을 구성할 수 있다.

 

N번 삽입 O(n log n)보다 좋은 성능을 기대할 수 있다.

 

 

Implementation

다음은 이론에서 배운 내용을 바탕으로 만든 최대힙이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Heap {
	vector<ll> heap;
	int last;

	Heap() {
		heap.push_back(0);
		last = 0;
	}

	void swap(ll& lhs, ll& rhs) {
		lhs ^= rhs; rhs ^= lhs; lhs ^= rhs;
	}

	void upheap(int id) {
		if (id == 1) return;
		if (heap[id] > heap[id / 2]) {
			swap(heap[id], heap[id / 2]);
			upheap(id / 2);
		}
	}
	void downheap(int id) {
		int tar = id;
		if (id * 2 <= last && heap[tar] < heap[id * 2]) tar = id * 2;
		if (id * 2 + 1 <= last && heap[tar] < heap[id * 2 + 1]) tar = id * 2 + 1;
		if (tar != id) {
			swap(heap[id], heap[tar]);
			downheap(tar);
		}
	}

	void push(ll v) {
		heap.push_back(v); last++;
		upheap(last);
	}
	void pop() {
		heap[1] = heap[last];
		heap.pop_back();
		last--;
		downheap(1);
	}

	ll top() {
		return heap[1];
	}
	bool empty() {
		return (last == 0);
	}
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	Heap H;
	int TEST; cin >> TEST; while (TEST--) {
		ll n; cin >> n;
		if (n == 0) {
			if (H.empty()) cout << "0\n";
			else {
				cout << H.top() << "\n";
				H.pop();
			}
		}
		else H.push(n);

		// for (auto i : H.heap) cout << i << " "; cout << "\n";
	}
}