[자료구조] Priority Queue : Heaps

DataStructure

[자료구조] Priority Queue : Heaps

식빵민 2022. 5. 30. 23:18

Priority queue (우선순위 큐) : 엔트리의 집합체를 저장하는 ADT.

Heaps : 이진트리 형태의 Priority Queue, 부모 노드의 우선순위가 자식 노드의 우선순위보다 높다.

출처 : https://velog.io/@thisisemptyyy/Data-Structure-004-Heap

Heap의 높이

height가 h일 때, heap이 갖는 노드의 수 n
full binary tree에서 노드가 하나 추가됐을 때, n = 1 + 2 + 3 + 4 +... + 2^(h-1) + 1
*full binary tree : internal 노드의 자식이 두 개고, external 노드의 depth가 같은 tree (완전 피라미드 형식!)
∴ n ≥ 1 + 2 + 3 + 4 +... + 2^(h-1) + 1
→ n ≥ 2^h
→ h ≤ log n

주요 메소드

* last node : external 노드끼리의 depth의 차이를 최소화한 상태에서 가장 오른쪽에 있는 external 노드

Insert(e) :
1. e를 last node로 설정 하여 삽입- O(1)
2. heap의 우선순위에 맞게 재 저장한다. (Upheap)
  - Upheap : 삽입된 노드를 재 저장할 때 사용하는 방법
    노드 추가 → 부모와 우선순위 비교 → 부모보다 우선순위 높으면 부모 노드와 위치 swap - swap 한번 : O(1)
    ∴ swap 한 번은 상수시간동안 수행, WorstCase일 때, height 만큼 swap해줘야 함 - O(log n)
  - UpdateLastNode() :
    1. 반복자 Iterator 포인터 설정 후, 부모노드의 왼쪽 자식일 때 까지 Iterator를 부모노드로 재설정
    2. 왼쪽 자식인 경우에, 부모노드의 오른쪽 자식으로 Iterator설정
    3. external 노드일 때 까지 Iterator를 왼쪽 자식 노드로 재설정
    4. 그때의 external 노드가 last node가 된다.
    5. WorstCase에 root까지 갔다가 다시 external 노드 까지, 약2log n - O(log n)
Remove(e) :
1. 임시변수에 e에 해당하는 값 복사
2. e삭제 후 last node를 e의 위치에 덮어쓰기
3. last node 삭제후 e위치에 last node를 우선순위에 맞추기 위해 재저장 (Downheap)
  - Downheap : 노드를 삭제할 때, 우선순위를 맞춰 재 저장하기 위한 방법
    root부터 시작 → 노드를 왼쪽자식, 오른쪽자식과 비교(왼쪽 자식먼저) → 우선 순위 안맞으면 swap - swap 한번 : O(1)
    ∴ swap 한 번은 상수시간동안 수행, WorstCase일 때, height 만큼 swap해줘야 함 - O(log n)
  - UpdateLastNode() :
    1. 반복자 Iterator 포인터 설정 후, 부모노드의 오른쪽 자식일 때 까지 Iterator를 부모노드로 재설정
    2. 오른쪽 자식인 경우에, 부모노드의 왼쪽 자식으로 Iterator설정
    3. external 노드일 때 까지 Iterator를 오른쪽 자식 노드로 재설정
    4. 그때의 external 노드가 last node가 된다.
    5. WorstCase에 root까지 갔다가 다시 external 노드 까지, 약2log n - O(log n)
수행시간
삽입 : O (log n)
삭제 : O (log n)
노드의 개수 : O (n)
∴ O(n log n) → SortedList, UnsortedList [둘다 O(n^2)] 보다 효율적임

Merging Two Heaps : Heap 합치기

두 Heap과 하나의 entry e가 주어진다.
e를 root로 설정하고, 두 Heap을 왼쪽 subtree와 오른쪽 subtree로 삽입해서 새로운 tree를 만든다.
우선순위를 맞추기 위해 DownHeap을 실행한다.
노드의 개수 :
- i의 height을 가진 두 full binary tree Heap이 있을때, 노드의 개수는 2^i - 1
- 새로운 Heap의 노드의 개수는 2(2^i - 1) + 1 = 2^(i+1) - 1

이 방식으로 새로운 Heap 만들기 : Bottom-up Heap construction

최초에 두 Heap이 단일 노드 두개로 주어진다.
Merging Two Heaps을 활용해 새로운 Heap 생성
만들어진 Heap 두개를 이용해 다시 Heap 생성
이를 계속하여 새로운 Heap을 만든다.

*노드의 개수 총 n개	depth	node의 수	swap 연산 수 *((h-depth)node의 수)**	비교 연산수 *(swap 연산 수 2)**
O / \ O O / \| \| \ O O O O . . . . o o o o .... o o o o	0	1	h * (1 = n/2^(log n))	h * { n/2^((log n) - 1) ≒ n/2^(log n) }
	1	2	(h-1) * 2	(h-1) * n/2^((log n) - 2))
	...	...	...	...
	h-2	약 n/8	2 * n/8	2 * n/4
	h-1	약 n/4	1 * n/4	1 * n/2
	h	약 n/2

∑(i = 1 ~ log n) i * n / 2^i = n*∑(i = 1 ~ log n) i / 2^i ≤ n*∑(i = 1 ~ ∞) i / 2^i

∑(i = 1 ~ ∞) i / 2^i

= X = 1 * 1/2 + 2 * 1/4 + 3 * 1/8 + ...

1/2 * X = 1 * 1/4 + 2 * 1/8 + ...

1/2 * X = 1/2 + 1/4 + 1/8 ... = (1/2)/(1 - 1/2) = 1

∴ X = 2

n*∑(i = 1 ~ ∞) i / 2^i = 2n

∴ Bottom up heap construction is O(n)

→ 단순히 생성하는 Heap보다 효율적

벡터로 구현하는 Heap

root값 1번 index에 저장 (0번 index는 비워둠)
root의 왼쪽자식 2번, 오른쪽자식 3번에 저장
i번의 왼쪽 자식 2i 번에, 오른쪽 자식 2i+1 번에 저장

//vector를 이용해 구현
class heap{
public:
    heap(){
        arr.push_back(0);
    }
    int size(){
        return (int)arr.size()-1;
    }
    bool empty(){
        return size()==0;
    }
    void insert(int e){
        arr.push_back(e);
        upheap(size());
    }
    int top(){
        if(empty()) return -1;
        else return arr[1];
    }
    void pop(){
        if(empty()) return ;
        swap(1,size());
        arr.pop_back();
        downheap(1);
    }
    void print(){
        if(empty()){
            cout<<-1<<endl;
            return ;
        }
        else {
            for(int i=1;i<=size();i++){
                cout<<arr[i]<<" ";
            }cout<<endl;
        }
    }
private:
    vector<int>arr;
    
    bool compare(int idx1, int idx2){
        if( arr[idx1] >= arr[idx2] )return true;
        else return false;
    }
    void swap(int idx1,int idx2){
        arr[0] = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = arr[0];
    }
    void upheap(int idx){
        if(idx == 1) return;
        int par = idx/2;
        if(compare(idx,par)){
            swap(par,idx);
            upheap(par);//par은 이전 idx
        }
    }
    void downheap(int idx){
        int left = 2*idx;
        int right = 2*idx+1;
        int child;
        if(left>size()) return;
        else if(left==size())child=left;
        else{
            if(compare(left,right))child = left;
            else child = right;
        }
        
        if(compare(child,idx)){
            swap(child,idx);
            downheap(child);
        }
    }
};
int main(){
    int t;
    cin>>t;
    heap H;
    string cmd;
    while(t--){
        cin>>cmd;
        if(cmd == "insert"){
            int i;
            cin>>i;
            H.insert(i);
        }else if(cmd == "size"){
            cout << H.size() << endl;
        }else if(cmd == "isEmpty"){
            if(H.empty()){
                cout<<1<<endl;
            }else cout<<0<<endl;
        }else if(cmd == "pop"){
            cout<<H.top()<<endl;
            H.pop();
        }else if(cmd == "top"){
            cout<<H.top()<<endl;
        }else if(cmd == "print"){
            H.print();
        }
    }
    return 0;
}

[자료구조] Priority Queue : Heaps

[자료구조] Priority Queue : Heaps