[ 우선순위 큐와 힙 ] 완전 이진 트리, heap의 구현 ( + 백준 11279번 최대힙)

 

🔎 우선순위 큐란?

 

기존의 큐는 먼저 넣은 요소가 먼저 나오는 FIFO( first in - first out )이지만,

우선순위 큐는 들어간 순서 상관없이, 우선순위가 높은 데이터가 먼저 나온다 !

(ex.위급한 사람부터 처치하는 응급실)

 

우선순위 큐는 힙(Heap)이라는 자료구조로 구현하며,

모든 연산에 대한 시간 복잡도가 O(log n)이다.

 

 

 

 

 

---

 

 

 

 

 

 

📖 완전 이진 트리와 힙

 

 

 

🔎 완전 이진 트리 (complete binary tree)

- 이진 트리(자식이 최대 2개인 트리)의 한 종류

- 마지막 레벨 제외하고는 모든 레벨이 다 채워져있어야 함

- 마지막 레벨의 모든 노드는 왼쪽부터 빈공간없이 채움

오른쪽은 완전 이진 트리가 아님 !

 

 

 

 

 

📍  힙(Heap)의 조건

1) 완전 이진 트리

2) 힙은 상위노드가 모든 하위노드보다 우선순위가 크거나 같다

 

 최소 최댓값을 찾을 때, 배열을 사용하면 O(n)의 시간복잡도가 걸리고, 배열은 삽입 삭제 연산이 O(n)까지도 걸리지만,

힙을 사용하면  O (1) 시간에 찾을 수 있고, 모든 연산에 대해 O(log n) 시간이 걸린다 !

 

최대 힙과 최소 힙

 

 

 

 

 

---

 

 

 

 

 

📚 힙의 삽입 & 삭제 연산

 

 

최대 힙을 기준으로 힙의 연산을 살펴보자.

➕ 삽입 연산

맨 마지막 자리에 일단 추가 - 부모자식 비교하며 자리 찾기

삽입 연산 예시

 

 

➖  삭제 연산

최대 힙(max heap) 기준, 삭제 연산은 최댓값을 가진 요소를 삭제하는 것

루트 노드 삭제 - 맨마지막 노드를 루트로 - 자식들 중 큰 것과 차차 비교하며 자리 찾기

 

삭제 연산 예시

 

 

 

 

 

 

---

 

 

 

 

 

📝 예시 문제로 알아보는 최대 힙의 구현

 

1) 배열과 2) 라이브러리 두 가지 방법으로 최대 힙을 구현해보쟈 ! :)

 

 

백준 11279번 최대 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

 

 

 

1. 배열(vector)로 최대 힙 구현

 

 

1. 구현을 쉽게 하기 위해서 인덱스 1부터 시작한다.
2. 인덱스
- 왼쪽 자식 인덱스 : (부모의 인덱스) * 2
- 오른쪽 자식 인덱스 : (부모의 인덱스) * 2 + 1
- 부모 인덱스 : (자식의 인덱스) / 2

 

 

#include <iostream>
#include <vector>

using namespace std;


// 힙 비어있는지 체크하는 함수
bool isEmpty(const vector<int>& q) { //벡터에 담긴게 처음 담아준 0밖에 없다면, 텅빈거야 !
    return q.size() == 1;
}


// 힙 삭제연산 함수
void pop(vector<int> &q) {
    
    q[1] = q[q.size()-1]; //마지막 노드를 루트 노드에
    q.pop_back(); //마지막 노드 삭제
    
    int parent = 1; 
    int child = 2;
    int biggerChild=0; // 더 큰 자식의 인덱스
    
    while(child < q.size()) {
        
        biggerChild = child;
        
        // 오른쪽 자식 노드 존재하고, 
        if(child<q.size()-1) {
            if(q[child] < q[child+1]) { // 오른쪽이 왼쪽보다 크다면, 
                biggerChild = child+1; // 오른쪽 자식의 인덱스를 biggerChild에 저장
            } 
        }
        
        // 부모가 자식보다 작으면 swqp
        if(q[parent] < q[biggerChild]) {
            swap(q[parent], q[biggerChild]);
            
            // 새 부모노드 기준으로 인덱스 업데이트
            parent = biggerChild;
            child = parent*2;
            
        } else { //부모가 크면, break
            break;
        }
    }
}

// 힙 삽입연산 함수
void insert(int x, vector<int> &q) {
    
    q.push_back(x); // x를 마지막 노드에 삽입
    
    int idx = q.size()-1; // x가 들어간 마지막 노드의 인덱스
    
    
    while(idx > 1) { // 삽입한 노드가 루트가기 전까지 비교 !!!
        //부모와 비교
        if(q[idx] > q[idx/2]) { // 자식인덱스 / 2 = 부모인덱스
            swap(q[idx], q[idx/2]);
            idx /=2;
        } else { // 부모보다 작다면, 자기 자리 찾은거니깐 ! break
            break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    
    int n, x;
    cin >> n;
    
    // 배열로 최대힙 구현
    vector<int> q;
    q.push_back(0);
    
    
    while(n--) {
        cin >> x;

        
        if(x) {
            // 삽입 연산
            insert(x, q); 
        } 
        
        else {
            // 삭제 연산
            
            //비어있다면 0 출력
            if(isEmpty(q)) {
                cout << "0\n";
            } 
            
            else {
                cout << q[1] <<"\n"; // 루트노드 출력
                pop(q);
            }
            
        }
    }

    return 0;
}

 

 

 

 

2. 우선순위 큐 라이브러리 이용

queue 헤더에 있는 우선순위 큐 라이브러리를 사용해서, pop, top, push 함수로 최대 힙 연산을 손 쉽게 처리할 수 있다 !

#include <iostream>
#include <queue>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    
    int n, x;
    cin >> n;
    priority_queue <int> max_heap; // 최대힙으로 우선순위 큐 구현
    
    
    while(n--) {
        cin >> x;

        
        if(x) {
            // 삽입
            max_heap.push(x);
        } 
        
        else {
            
            //비어있다면 0 출력
            if(max_heap.empty()) {
                cout << "0\n";
            } 
            
            // 삭제
            else {
                cout << max_heap.top() << "\n";
                max_heap.pop();
            }
            
        }
    }

    return 0;
}