[Algorithm] 최대힙(priority_queue : 우선순위 큐)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 자연수가 입력되면 최대힙에 입력

     - 숫자 0 이 입력되면 최대힙에서 최댓값을 출력

       ( 출력할 자료가 없으면 -1 출력)

     - -1 이 입력되면 프로그램 종료

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

C++ STL 에서 제공해주는 priority_queue 를 알아야 이 문제를 풀어낼 수 있을 것이다.

ㅇ최대힙(max heap)

  - 완전이진트리로 구현된 자료구조

  - 부모 노드값이 왼쪽 자식과 오른쪽 자식 노드의 값보다 크게 트리가 구성

  - 트리의 root 노드는 입력된 값들 중 가장 큰 값이 저장.

5 3 2 1 4 6 7 순으로 입력하였을 때 최대힙 트리에서 일어나는 상황을 그려보자.

5 를 입력

3을 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

3은 5보다 작으므로 부모 노드와 교환이 일어나지 않음.

2를 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

2는 5보다 작으므로 부모 노드와 교환이 일어나지 않음.

1을 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

1는 3보다 작으므로 부모 노드와 교환이 일어나지 않음.

4을 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

4는 3보다 크므로 부모노드와 교환이 일어나야 한다.

부모 노드와 교환

6을 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

6은 2보다 크므로 부모노드와 교환이 일어나야 한다.

부모노드와 교환

교환하고도 부모 노드 5 보다 크다.

부모 노드와 또 교환!

7을 입력 (입력될 때는 가장 마지막 노드 자리에 입력)

7은 5보다 크므로 부모노드와 교환이 일어나야 한다.

부모 노드와 교환

교환하고도 부모 노드 6 보다 크다.

부모 노드와 또 교환!

이러한 과정이 일어난다. 

하지만, priority_queue 에서는 push 만 해주면 알아서 이 과정을 수행한다.

priority_queue 자료구조를 사용하기 전 동작하는 과정은 알아두면 좋을 것 같아

귀찮지만 그려보았다.

#. Code

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

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n;     priority_queue<int> pQ;       while(true)      {         scanf("%d", &n);           if (n == -1)             break;           if (n == 0)         {             if (pQ.empty())                 printf("-1\n");             else             {                 printf("%d\n", pQ.top());                 pQ.pop();             }         }         else             pQ.push(n);     }       return 0; } Colored by Color Scripter

cs

line 19) '-1' 이 입력되면 프로그램 종료

line 22~31) 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력 (최대값을 꺼낸 후 pop 을 수행해주어야 함)

          출력할 자료가 없다면 '-1' 출력

line 33) 자연수가 입력되면 최대힙에 입력

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<stdio.h> #include<queue> #include<vector> using namespace std;   int main(){     int a;     priority_queue<int> pQ;       while(true){         scanf("%d",&a);         if(a==-1) break;         if(a==0){             if(pQ.empty()) printf("-1\n");             else{                 printf("%d\n", pQ.top());                 pQ.pop();             }         }         else pQ.push(a);     }       return 0; } Colored by Color Scripter

cs

#. Result

  - Input --------------------------------------------------------

5 

3 

6 

0 

5 

0

2 

4 

0 

-1

------------------------------------------------------------------

  - Output --------------------------------------------------------

6

5

5

------------------------------------------------------------------