How We Coding

<180709> 우선순위 큐 (Priority Queue)

Tutoring/SRF - B2018. 7. 10. 00:10

<180709>


### 우선순위 큐 ###


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
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
cs


>> Min Heap 으로 구현.

>> 루트의 인덱스는 1로 두고 구현.

>> push() : n번째 노드는 완전이진트리 기준 n번째 위치를 cur로, cur의 부모 인덱스를 p로 두고 시작.    

   부모노드와 비교하여, 현재 노드값이 부모노드의 값보다 작으면, 부모노드의 값을 현재노드 위치로 당긴다. (35라인)

   보통 스왑을 하지만, 나중에 자기 위치만 찾은다음 대입만 해주는 식으로 구현을 하였다.

   부모의 인덱스가 0이라는 것은 더이상 부모가 없다는 뜻. 즉, 15라인은 부모가 존재하는데, 부모의 값보다 대상 데이터의 값이 작다면 이과정을 반복.

>> pop() : 팝은 맨 마지막 데이터를 루트에 두고 자기자리를 찾아가는 과정으로 생각하면 된다.

  자기 자리를 찾아갈때는, 자식의 인덱스가 전체 사이트의 크기보다 작은지를 확인하면 된다. 

  자식의 인덱스가 사이즈보다 크다는 것은 더이상의 자식이 존재하지 않는다는 뜻.

  그리고 자식이 존재하는데(child < size), 두개의 자식이 존재한다면(child+1 < size) 둘중 작은 값을 가진 자식과 교환을 해야한다.!!


>> 구현 아이디어는 윤성우의 열혈 자료구조 + 생능 출판사의 천인국 저자 책. 학교 교잰데 이름 기억안남;;


<문제풀이>


[1927]  최소 힙 : http://boj.kr/1927


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
66
67
68
69
70
71
72
73
74
75
76
/*** Min Heap ***/
/*** boj.kr/1927 ***/
 
#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<int> pq;
    while(n--) {
        int k;
        cin >> k;
 
        if(k) pq.push(k);
        else {
            int ans;
            if(pq.empty()) ans = 0;
            else {
                ans = pq.top();
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 
cs




[11286] 절대값 힙 : http://boj.kr/11286


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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <vector>
#define MAXN    100000
 
using namespace std;
 
typedef pair<int, int> pii;
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && (heap[p].first > data.first || ((heap[p].first == data.first) && (heap[p].second > data.second)))) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size) {
                if(heap[child].first > heap[child+1].first) child++;
                else if(heap[child].first == heap[child+1].first) {
                    if(heap[child].second > heap[child+1].second) child++;
                }
            }
            if(heap[size].first > heap[child].first || ((heap[size].first==heap[child].first)&&(heap[size].second > heap[child].second))) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
 
};
 
int main()
{
    int n;
    scanf("%d", &n);
 
    Priority_queue<pii> pq;
    while(n--) {
        int k;
        scanf("%d", &k);
 
        if(k) {
            int tmp = k < 0 ? -k : k;
            pq.push(pii(tmp, k));
        }
        else {
            int ans;
            if(pq.empty()) ans=0; 
            else { ans = pq.top().second; pq.pop(); }
            printf("%d\n", ans);
        }
    }
}
 
cs


>> 절대값이 같으면 원래값이 작은 순으로 MinHeap 구현


>> 힙 구현한것을 바꾸지 않고 하는 방법 (referenced by kyujeong)


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
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<double> pq;
    while(n--) {
        double k;
        cin >> k;
 
        if(k > 0) pq.push(k+0.1);
        else if(k < 0) pq.push(-k);
        else {
            int ans;
            double top;
            if(pq.empty()) ans = 0;
            else {
                top = pq.top();
                if(top == (int)top) ans = -(int)top;
                else ans = (int)top;
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 
cs




<멘토님 코드> 


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 <cstdio>
using namespace std;
const int MAXN = 1e5 + 6;
 
template<typename T>
void swap(T *a, T *b) {
   T tmp = *a;
   *a = *b;
   *b = tmp;
}
 
template<typename T>
struct priority_queue {
   T arr[MAXN];
   int idx;
 
   priority_queue() :idx (0) {}
 
   bool empty() { return idx == 0; }
 
   int size() { return idx; }
 
   T top() { return arr[0]; }
 
   void push(T const &data) {
      arr[idx++] = data;      
      int curr = idx - 1;
      while (1) {
         if (curr == 0) break;
         int par = (curr - 1) / 2;
         if (arr[par] > arr[curr]) swap(&arr[par], &arr[curr]);
         curr = par;
      }
   }
 
   void pop() {
      arr[0] = arr[--idx];
      int curr = 0, next;
      while (curr * 2 + 1 < idx) {
         next = curr;
         if (arr[next] > arr[curr * 2 + 1]) next = curr * 2 + 1;
         if (curr * 2 + 2 < idx && arr[next] > arr[curr * 2 + 2]) next = curr * 2 + 2;
         if (next == curr) break;
         swap(&arr[curr], &arr[next]);
         curr = next;
      }
   }
};
 
int main() {
 
   priority_queue<int> pq;
   int n;
   scanf("%d", &n);
 
   for (int i = 0,d ; i < n; i++) {
      scanf("%d", &d);
      if (d == 0) {
         if (pq.empty()) printf("0\n");
         else printf("%d\n", pq.top()), pq.pop();
      }
      else pq.push(d);
   }
   return 0;
}
cs


>> 종만북을 많이 참고한 코드라고 한다.

티스토리툴바