[자료구조] Priority, Heap

priority queue : 우선순위를 보장하면서, 아이템을 보관한다. 
높은 우선순위를 가지는 아이템이 먼저 나온다. (큐의 기본 개념인, FIFO가아니다)
 
예를 들어, stack, queue를 priority queue로 구현할수가 있다.
 

자료구조	elements to be removed
stack	가장 최근 데이터(LIFO)
queue	처음에 들어온 데이터(FIFO)
Priority queue	highest priority data

적용된 예시로는, 시뮬레이션 시스템(event time에 우선순위를 둔), 네트워크 프로토콜 컨트롤, OS의 스케쥴링
 
 

Priority Queue Types

minimum priority queue / maximum priority queue 이렇게 두가지가 있다.
 

Implementation

using ... array, linked list, heap!

 
이때, 구현에 사용되는 자료구조에 따라 시간복잡도는 달라지게된다. 다음 표를 보자

자료구조	삽입 operation	삭제 operation
Unordered array	O(1)	O(n)
Unordered linked list	O(1)	O(n)
Ordered array	O(n)	O(1)
Ordered linked list	O(n)	O(1)
Heap	O(logn)	O(logn)

> 삽입의 경우, 정렬되지않은 배열/리스트에는 그냥 추가해주면된다. 다만, 삭제시에는 그 element를 찾아야하므로, 전체를 돌며 찾아야한다. 그래서O(n)

정렬된 경우에는 반대이다. 넣어줄때 규칙을 지켜서 넣어주어야하므로, 그 자료구조를 돌며 적합한 위치를 찾는다 O(n).
삭제의 경우에는 정렬되어있으므로, 그냥 인덱스 찾아서 제거해주면된다. 그래서 O(1)
 
반면, Heap의 경우, 삽입과 삭제가 모두 O(log n)수준에 그쳐있다.
이제 힙이 무슨 자료구조인지 알아보자
 

Heap

: complete binary tree satisfying the following conditions

• Max heap : $key(parent node) ≥ key(child node)$
• Min heap : $key(parent node) ≤ key(child node)$

n개의 node를 가진 heap의 $height = O(log₂n)$
*heap은 complete binary tree : 모든 레벨이 노드로 꽉차있고, 부모 아래 노드 두개 무조건, 마지막레벨을 제외하곤
*즉, 마지막 level을 제외하고 $2^(i-1)$ nodes at level i

 
Heap Implementation
힙은 array를 통해 구현할 수 있다. : 꽉찬 binary tree이므로, 각 노드는 넘버링될 수 있다! 이를 index로 생각하자.

 

• $Parent node of node i : i/2$
• $left child node of node i : 2i$
• $Right child node of node i : 2i+1$

 
 
 
 
Max Heap의 insertion

1. new node는 heap의 last node의 다음에 삽입한다.
2. 삽입한 노드부터 루트 노드까지 경로에 있는 모든 노드들끼리 비교 이후에, heap priority를 만족시키기 위해 자리를 바꾼다.
(min heap도 유사하니 잘 생각하자)
3. key값 k가 부모노드의 키보다 작다면 terminates!

Time complexity $O(log₂n)$
 
 
Deletion
1. 루트노드를 지운다.
2. last node를 root node로 옮긴다.
3. 루트노드에서부터, 리프노드까지 비교하고, priority에 맞추어 자리를 바꾼다.
Time complexity $O(log₂n)$ 4. 키값이 chiled node보다 크거나 같을 때, comparison을 terminate!
Time complexity $O(log₂n)$

 
 
힙을 만들 때 주의해야하는것은, 부모/자식을 한번 비교만 하고 끝내는게아니라, 바꾼 뒤의 아래딸려있는 애들이랑 한번 더 비교를 해줘야한다.

나처럼 이러면안됨.

void build_max_heap(HeapType *h)
	{
		// Implement this function here.
		//힙은 자료구조 배열을 사용하지.... 즉 자식은 부모*2 [부모 자식1 자식2 자식1-1 자식1-2 자식2-1 자식 2-2 | 1-1-1 | 1-1-2 | 1-2-1] // 뒤에 다섯개가 비교대상
		int parent  = (h->heap_size)/2;
		element temp;
		int child;
		while (parent >= 1) {
			int lchild = parent*2;
			int rchild = parent*2 + 1;
			//종료조건을 설정해주지않아서, 사이즈보다 커지는걸 생각하지않았다.
			if (lchild>h->heap_size) {
				//parent--
				continue ; // 이건 그냥 기존코드가 이상한경우이다.;
			}
			if (rchild>h->heap_size) child = lchild;
			else if (h->heap[lchild].key > h->heap[rchild].key)
				child = lchild;
			else child = rchild;
			if (h->heap[parent].key < h->heap[child].key) {
				temp.key = h->heap[parent].key;
				h->heap[parent].key = h->heap[child].key;
				h->heap[child].key = temp.key;
			}
			parent--;

		}
	}

=> 코드를 보자. 부모를 줄여가면서 자식이랑 비교하는 코드이다. 내가 처음에 짰던 코드이다. 종료조건도없었고,