새싹교실/2014/다빈치인재반/10회차 (rev. 1.15)
- Priority_Queue
- Heap
- Heap 구현
- STL에서 Priority_Queue 사용
- Heap Sort
3.1. Priority Queue ¶
- In computer science/data structures, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
- While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
- 출처 : http://en.wikipedia.org/wiki/Priority_queue
3.2. Priority Queue in STL ¶
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
using namespace std;
priority_queue <int> pq;
int v[100];
int main(void)
{
int n = 10;
srand(time(NULL));
printf("Vector \n");
for(int i = 0; i<n; i++){
v[i] = rand() % 100;
printf("%d ", v[i]);
}
printf("\n\n");
for(int i = 0; i<n; i++){
pq.push(v[i]);
}
printf("Priority Queue \n");
while(!pq.empty()){
printf("%d ", pq.top());
pq.pop();
}
printf("\n\n");
}
- 힙(Heap)은 특별한 트리를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 heap 속성(property)을 만족한다.
- A가 B의 부모노드(parent node) 이면, 힙(heap) 에 적용된 것과 같은 순서로 key(B)에 관해서 key(A)는 순서가 정해진다.
힙에는 내림차순인 '최대 힙'과 오름차순인 '최소 힙'이 있다.
