[[TableOfContents]]
= 계획 =
 * Priority_Queue
 * Heap
 * Heap 구현
 * STL에서 Priority_Queue 사용
 * Heap Sort
 
= 참여자 =
||강사 || [권영기] ||
||<|10> 참여자|| [권준혁] ||
|| [이지수] ||
|| [김정민] ||
|| [유재범] ||
|| [] ||
|| [] ||
|| [] ||
= 내용 =
== 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]
== 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");
}
}}}
 * priority_queue : [http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue]
== Heap ==
 * 힙(Heap)은 특별한 트리를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 heap 속성(property)을 만족한다.
 * A가 B의 부모노드(parent node) 이면, 힙(heap) 에 적용된 것과 같은 순서로 key(B)에 관해서 key(A)는 순서가 정해진다.
힙에는 내림차순인 '최대 힙'과 오름차순인 '최소 힙'이 있다.
 * 각 노드의 children 의 최대개수는 heap 의 종류에 따라 다르지만, 많은 타입에서 children 의 개수는 2개 이하이다. 그리고 이것은 이진 힙(binary heap)으로 알려져 있다.
 * 출처 : [http://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)]
 
 * Heap Visualization - [http://www.cs.usfca.edu/~galles/visualization/Heap.html]
 * A heap data structure should not be confused with the heap which is a common name for the pool of memory from which dynamically allocated memory is allocated. The term was originally used only for the data structure.
== Binary Heap ==
 * 출처 : [http://en.wikipedia.org/wiki/Binary_heap]
=== Property ===
 * Shape property
   The tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Heap property
 * Heap property
   All nodes are either greater than or equal to or less than or equal to each of its children, according to a comparison predicate defined for the heap.
=== Operation ===
 * Max Heap 이라고 가정하자.
 * 삽입
  1. 가장 마지막 위치에 원소를 삽입한다.
  2. 삽입 한 원소를 원소의 부모와 비교한다. 만약 부모가 더 크다면 멈춘다.
  3. 부모가 더 작다면, 부모와 위치를 바꾼다. 그리고 다시 그 위치에서 부모와 비교...
 * 삭제 
  1. Root의 원소를 제거하고, Root에 Heap에 가장 마지막 위치에 있는 원소를 놓는다.
  2. 새로운 Root와 Root의 자식과 비교한다. 만약 Root가 더 크다면 멈춘다.
  3. Root가 더 작다면, 자식과 위치를 교체한다. 그리고 다시 그 위치에서 자식과 비교...
=== Implementation ===
== Heap Sort ==
 attachment:heapsort_animation.gif
 * 간단한 설명 : [http://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC]
 * Heap Sort Visualization - [http://www.cs.usfca.edu/~galles/visualization/HeapSort.html]
== Application of Priority Queue ==
 * Dijkstra's algorithm : 최단 경로를 구하는 알고리즘인데 그래프 시간에 배웁니다.
 * [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue]
 * Best-first search algorithms
 * Prim's algorithms
 * 그 외에도 여러가지 등등등..
= 후기 =

= 숙제 =
 * Binary Heap 구현 하기.
----
[새싹교실/2014], [새싹교실/2014/다빈치인재반]