알고리즘 기술

우선순위 큐

헐랭미 2020. 6. 23. 11:37

== max_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
 
int arr[10] = { 5,1,2,6,4,2,5,1,2,8 };
int n = 10;
 
int pq[100000];
int pq_size = 0;
 
void max_pq_add(int a)
{
    pq[++pq_size] = a;
 
    int child = pq_size; // child가 먼저 나오는게 편하다.
    int parent = child / 2;
 
    while (parent >= 1 && pq[parent] < pq[child]) 
    {                       // min_pq 는 여기서 부등호만 바뀐다.
        swap(pq[parent], pq[child]);
        child = parent;
        parent = child / 2;
    }
}
 
void max_pq_pop()
{
    cout << pq[1] << ' ';
    
    pq[1] = pq[pq_size--];
 
    int parent = 1;
    int child = parent * 2;
 
    while (1)
    {
        if (child + 1 <= pq_size && pq[child] < pq[child + 1])
            child = child + 1;
 
        if (child > pq_size || pq[parent] >= pq[child])
            break;
 
        swap(pq[parent], pq[child] );
        parent = child;
        child = child * 2;
    }
 
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    for (int i = 0; i < n; i++)
        max_pq_add(arr[i]);
 
    for (int i = 0; i < n; i++)
        max_pq_pop();
 
}
 cs