우선 순위 큐 (힙정렬) STL 사용하기

#include<stdio.h>

#include<queue>

using namespace std;

int main(){



#define _MAX_HEAP // 이곳을 생략시키면 MIN_HEAP!



#ifdef _MAX_HEAP

    priority_queue<int> a;

#endif



#ifndef _MAX_HEAP

    priority_queue<int, vector<int>, greater<int> > a;

#endif



    int x,i;



    for(i=1;i<=5;i++){

        scanf("%d",&x);

        a.push(x);

    }

    for(i=1;i<=5;i++){

        printf("%d",a.top());

        a.pop();

    }

    return 0;

}

입력받으며 정렬을 해야 할 때, 아주 큰 위력을 발휘하는 힙정렬!

최댓값이 루트가 되는 MAX 힙의 경우에는 "priority_queue<int> 변수;" 로,

최솟값이 루트가 되는 MIN 힙의 경우에는 "priority_queue<int, vector<int>, greater<int> > 변수;" 로 쓰면 된다.

 

Ps. 힙에 대한 설명 및 구현 방법은 http://blog.naver.com/hachn?Redirect=Log&logNo=103871306 에 잘 나와있으니 필요하면 찾아볼 것!