Priority Queue & Heap
1. Priority Queue
1.1 문제 상황
삽입은 자유롭게 이루어지지만, element를 꺼낼 때 항상 가장 큰 element(removemax)를 꺼내고자 한다면 가장 좋은 자료구조는 무엇인가?
ex) multi-tasking operating system에서 scheduling job하는 문제!
1.2 Unsorted array or linked list
insert : O(1)의 시간 소요
removemax : max인 element를 찾기 위해 O(n)의 시간 소요
1.3 Sorted array of linked list
insert : O(n)의 시간 소요, sorting을 위해
removemax : 맨끝 값을 return하면 되니까 O(1)
하지만 이때 heap 자료구조를 사용하게 되면 insert와 removemax 모두 O(logn)에 가능하다!
2. Heap
2-1. 정의
complete binary tree이며, 두가지 종류로 나뉘어진다.
Min-heap : 모든 부모 노드는 자식 노드보다 작다.
Max-heap : 모든 부모 노드는 자식 노드보다 크다.
Binary Search Tree와 다르게 partially ordered되어 있다.
-> max heap의 경우, parent는 child보다 크지만 child끼리는 따로 ordered 되어 있지 않음.
-> BST의 경우, 왼쪽 자식, 부모 노드, 오른쪽 자식이 각각 크기에 따른 순서가 정해져 있음(completely ordered)
Heap의 경우 보통 array-based complete binary tree로 구현된다!!
2-2. Max Heap Property
positions of leaf nodes in a max heap with n nodes : floor($\frac{n}{2}$)
그래서 max heap에서는 n - floor($\frac{n}{2}$)의 leaf nodes를 가진다.
왜?
-> index로 생각해보면 편함
2-3. Max Heap Implementation
boolean isLeap(int pos){ return (pos >= n/2) && (pos < n); }
int leftchild(int pos){
if(pos >= n/2)
return null;
return 2*pos + 1;
}
int rightchild(int pos){
if(pos >= (n-1)/2)
return null;
return 2*pos + 2;
}
int parent(int pos){
if(pos == 0)
return null
return (pos-1)/2 ;
}
대부분 간단히 구현 가능한 메소드(array-based)!
2-4. Building Heaps(sift down)
binary tree에서 Heaps 구조로 만들 때
sift down method를 사용한다.
귀납법을 이용하는 방법인데,
이미 left subtree와 right subtree에 heap이 구현되어 있다고 생각하고 R을 적절한 위치에 놓는거다.
만약
1. R이 H1, H2보다 크다면? 움직일 필요 없음!
2. R이 H1, H2보다 작다면? max(H1, H2)를 R과 자리를 바꾼다. => 그래야 양 자식들이 부모 노드보다 작게 됨!
이를 자식 노드로 이어가면서 계속 반복한다.
public void buildheap(){
//부모인 노드를 대상으로 siftdown를 수행
for (int i = n/2-1; i>=0; i--) siftdown(i);
}
private void siftdown(int pos){
assert (pos >= 0) && (pos < n) :
"Illegal heap position";
while(!isLeaf(pos)) {
int j = leftChild(pos);
//오른쪽 자식 노드가 더 크면 오른쪽 자식 노드로 j 변경
if((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0))
j++;
//root node가 자식 노드들보다 크거나 같으면 종료
if(Heap[pos].compareTo(Heap[j]) >= 0){
return;
}
//root node가 자식 노드보다 작으면 swap
DSutil.swap(Heap, pos, j);
//pos 위치가 j로..
pos = j;
//pos가 제자리를 찾거나 leaf에 갈 때까지 반복
}
2-5. RemoveMax, Insert
public E removemax() {
if(n == 0)
System.out.println("Removing from empty heap");
//root node를 Heap[n]으로 보냄.
DSutil.swap(Heap, 0, --n);
if(n != 0) siftdown(0);
return Heap[n];
}
public void insert(E val){
asssert n < size:
"Heap is full";
int curr = n++;
Heap curr = val;
//Siftup until curr parent's key > curr key
while((curr != 0) && Heap[curr].compareTo(Heap[parent(curr)] > 0)){
DSutil.swap(Heap, curr, parent(curr));
curr = parent(curr);
}
}Removemax의 경우 worstcase가 바꾼 n node가 그대로 leaf로 떨어지는 경우이다.
$\theta(logn)$이 걸림 => depth의 크기
Insert 시에 n개의 value를 root에 넣는다면 총 $\theta(nlogn)$의 시간이 걸리겠지만
가장 아래의 node에 넣는다면 대부분의 node들이 아래에 몰려있기 때문에($2^h$) 많은 거리를 움직이지 않게 된다.
i를 1로 시작하는 바닥부터 세는 레벨이라고 할 때
$$\sum_{i = 1}^{\log n} (i - 1) \frac{n}{2^i} = \frac{n}{2} \sum_{i-1}^{\log n} \frac{i - 1}{2 ^ {i-1}} = \theta(n)$$
$$\sum_{i = 1}^n \frac{i}{2^i} = 2 - \frac{n+2}{2^n}$$
After insert and removemax, Heap remains as complete binary tree.