힙

우선 순위 큐를 구현하는 데 쓰이는 자료구조이다.

힙의 기본 : 부모 노드는 자식 노드보다 우선순위가 높다. (몇 년 전에는 이진트리의 기본과 헷갈렸던 것 같다 )

삽입의 기본 : 제일 끝에 추가한 뒤, 부모와 자리를 바꾸면서 본인 우선순위에 맞는 곳을 찾는다.

삭제의 기본 : 요소 1을 반환한 뒤, 제일 끝 노드를 1로 가져와서 자식과 자리를 바꾸면서 본인 우선순위에 맞는 곳을 찾는다.

힙이 아닌 배열을 힙으로 만들기 위해서는 시간 복잡도 O(nlogn)이 들지만, PS에서 쓰지 않는다.(어차피 힙으로 쓸 자료구조라는 전제 하에 그걸 사용하므로)

아래 코드에서 일반적인 코드와 차별점을 둔 것은 삽입 정렬때와 비슷한 것인데,
데이터가 들어가는 곳부터 진행하면서 스와핑을 하지 않고, 스와핑없이 밀기만 하다가 위치를 찾으면 그 곳에 데이터를 넣어주는 것이다. 

물론, 힙 추가, 삭제의 시간 복잡도 O(logn)이므로 만 ~ 십만 단위의 자료에서 몇 십밖에 되지 않으므로 눈에 띄는 최적화는 아니다. 

데이터의 자료형이 int형이라고 가정한 힙의 추가, 삭제 코드이다.

void push(int val) {
	int t = ++heap_size;
	while (t>1) {
		if (val < heap[t / 2]) {
			heap[t] = heap[t / 2];
			t = t / 2;
		}
		else break;
	}
	heap[t] = val;
}
int pop() {
	int ret = heap[1];
	int v = heap[heap_size--];
	int parent = 1, child = 2;
	while (child<=heap_size) {
		if (child + 1 <= heap_size)
			if (heap[child] > heap[child + 1])child++;
		if (v > heap[child]) {
			heap[parent] = heap[child];
			parent = child;
			child = parent * 2;
		}
		else break;
	}
	heap[parent] = v;
	return ret;
}