Jeonghun (James) Lee

11/01/2016

Heap 과 Heap sort 와 Priority Queue

1. Heap 이란?

기본구조

Heap은 일종의 이진트리 구조로 구성이 되며 (Binary Tree)
여기서 간단한 한가지 특징 존재한다.

항상 Parent Node 와 Child Node의 대소관계가 분명해야하는 것이다.

그래서, 아래와 같이 두가지 종류의 Heap Tree가 만들어 질수 있다.

top-heavy tree : Parent Node > Child Node( Left, Right)
bottom-heavy tree : Parent Node < Child Node( Left, Right)

이곳에서는 Left Node와 Right Node의 대소관계는 중요하지 않으며,

오직 Parent Node와 Child Node의 대소관계만 따진다.

기본적인 Heap이 완성된 경우의 구조

top node는 top-heavy tree의 경우 가장 큰 값
top node는 bottom-heavy tree의 경우 가장 작은 값
위에서 언급했듯이, 그 다음 작은 값은 child 중 한 Node (Left or Right)

Heap의 기본특성

Parent node와 Child node의 대소관계가 분명하다.
Left node와 Right node의 대소관계의 불문명하다.
오직 Parent와 Child node의 구성만 알수 있다.
heap은 기본적으로 왼쪽 평형트리 구조를 가지고 있으며, 이는 중요하다.

상위 4번 특성 (왼쪽 평형트리 구조) 로 아래의 추가적인 특성이존재

Node 추가 할 경우,Child node가 추가되는 방향은 항상 왼쪽에서 오른쪽.
Node 삭제 or 추가된 경우 Child node가 한개가 될 경우 left node 우선순위가 있음
Binary 탐색을 한다면 BFS 방식

*BFS(Breadth-first search) 대표적인 이진 트리의 탐색 알고리즘으로 넓이 우선 순위이다.

Timer complex 설명

아래 설명에도 자세히 나와 듯이 기본적으로 Binary Tree 구조이며,
시간의 복잡도는 Insert 할 경우는 Worst Case O(LogN)이다.

https://en.wikipedia.org/wiki/Binary_heap

1.2 Heap 기본구현 (Array 방식)

기본적으로 Array로 구현하는 것은 아래와 같으며, 아래와 같은 성질이 존재한다.
기본성질 Array Binary Tree 기본 성질 array를 0부터 사용할 경우

Number Node

Number of Node = 2^(i+1) -1 , N 은 Tree의 Level의 수

Array즉 배열을 이용하여 이진 트리를 구성해야하기 때문에 Array와 binary Tree의 성질
알아야한다.

Array로 Binary Tree 구현할 경우 기본성질

Left Node = 2i+1
Right Node = 2i+2
Parent Node = (i-1)/2

https://en.wikipedia.org/wiki/Binary_tree

자세한 내용은 2.2 Data의 정적구현 참조

http://ahyuo79.blogspot.com/2016/10/tree.html

top-heavy heap 구현방법

top-heavy heap는 top node는 가장 큰 값을 소유하고 있다.
Heap의 Length을 정확히 파악하여 last node의 parent와 child 대소 관계를 비교
Child가 큰 경우에만 Parent와 Child 교환진행
왼쪽 Parent로 이동가며 Top Node까지 진행하며 3번 반복 (방향 오른쪽 -> 왼쪽 )

Top-heavy heap Example

상위그림 기준으로 보면, Last Node 14이며 , Parent 6 여기서 3 Node를 비교 교환시작.
Parent 6,5,4,3,2,1,0 비교와 교환 진행 하면 Top-heavy heap 구축된다.

Heap 자료구조 관련내용
http://opendatastructures.org/ods-java/10_1_BinaryHeap_Implicit_Bi.html
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
https://en.wikipedia.org/wiki/Heap_(data_structure)

2. Heap Sort

기본적으로 상위 Heap 구현이 된 후에, 이를 이용한 Sort 알고리즘이다.
방법은 간단하며, Heap 기본성질이 최대 or 최소 값을 추출하는 방법을 이용한다.

구현방법

n 개의 노드를 가진 top-heavy heap 구조 구축
top-heavy heap는 top node는 가장 큰 값을 소유
top-node를 last node와 교환진행 (top-node 추출작업과 동일)
top-heavy heap를 재구축을 heap size를 1을 줄이고 진행한다.

top-heavy heap 재구축 및 추출작업

top-node가 현재 작은값이기때문에 child 중 두번째로 큰 값을 찾아 교환
원래 top-node의 값은 child (left or right) 되었기에 관련 Tree는 비교 및 교환진행
2번을 반복하며 방향은 아래로 지속적으로 한쪽 방향으로만 비교 및 교환진행 ( O(logN)

아래의 예제들을 보면, heapify가 heap을 구성한다.
https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://en.wikipedia.org/wiki/Heapsort

다른 Heapsort 예제들
http://thinkpro.tistory.com/72
http://ehclub.co.kr/1552

3. Priority Queue

기본적으로 상위 Heap 구현이 된 후에, 이를 이용한 우선순위 Queue를 구현이 가능하다.
Heap sort 와 마찬가지로, Heap의 기본성질인 가장 큰 값 or 가장 작은 값을 이용하는 것이다.
Priority Queue 역시 Heap의 기본 성질을 원하는 것이기 때문에, Heap를 이용하여 쉽게
구현이 가능하다.

array 구현방법 (정적으로 구현방법)

pqueue_init : n 개의 노드를 가진 상위 top-heavy heap 구성
pqueue_insert: 기존의 top-heavy heap 의 마지막 노드에 data 를 삽입 후 다시 heap화 한다.
pqueue_extract: top node를 추출하고 size를 줄이고 다시 heap화 한다.

구현함수

pqueue_init : 상위 heap 구성과 동일
pqueue_insert : pqueue_init와 동일
pqueue_extract: top-heavy 재구축과 동일

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90
https://en.wikipedia.org/wiki/Priority_queue

Heap and Heap sort and Priority Queue 예제

구글링하다가, 이해하기 쉬운 C source를 찾으려고 했으나, 찾을수 없어 wiki 기반으로,
이해가며, 그냥 내가 다시 구현했다.

	#include <stdio.h>
	//refer to https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

	#define heap_parent(n) ((n-1)/2)
	#define heap_left(n) ((2*n)+1)
	#define heap_right(n) ((2*n)+2)

	typedef enum{
	SET_HEAPNULL=0,
	SET_UPHEAP,
	SET_DOWNHEAP,
	}HEAP_DIRECTION;

	#define TOP_HEAVY_HEAP

	void printarry(int arry[],int lens) //debug
	{
	int i;

	printf("----( arry lens=%d )\n",lens);
	for(i=0;i<lens;i++)
	printf("[%02d] ",arry[i]);
	printf("\n");

	}

	void swap(int a[], int b[])
	{
	int tmp;
	static int cnt=1;
	// printf("%d swap %d %d \n",cnt++,a,b); //debug
	tmp = *a;
	a = b;
	*b = tmp;
	}

	int makeheap(int * arr, int pos, int heap_size, int updown)
	{
	int left, right, parent;

	if(updown == SET_HEAPNULL)
	return -1;

	while(pos < heap_size) // this loop is only for extracting top-node and direction: SET_DOWNHEAP
	{
	left = heap_left(pos);
	right = heap_right(pos);
	parent = pos; /* 1. compare an parent with two children (left,right)
	2. get the largest value
	3. heap_size means heap's length */

	#if defined(TOP_HEAVY_HEAP)
	if(( left < heap_size) && (arr[left]>arr[parent]))
	parent = left;
	if((right < heap_size) && (arr[right]>arr[parent]))
	parent = right;
	#else
	if(( left < heap_size) && (arr[left] < arr[parent]))
	parent = left;
	if((right < heap_size) && (arr[right] < arr[parent]))
	parent = right;
	#endif

	if(parent == pos) break; // now is the largest value,

	swap(&arr[pos], &arr[parent]); // pos is the largest value after swap

	if(updown == SET_UPHEAP) break; //if used makeupheap, not working loop
	pos = parent; // for down heap

	}

	if(updown == SET_DOWNHEAP){
	printarry(arr,heap_size); // debug
	}

	}


	void makeupheap(int *arr, int length) // for inserting new nodes , direction: SET_UPHEAP , up
	{
	int parent=length-1; //last node

	for(parent=heap_parent(parent); parent >=0; parent--) //check from a parents of last node to top node
	makeheap(arr, parent, length,SET_UPHEAP);

	printf("after new built up-Heap lens=%d (up) \n",length); // debug
	printarry(arr,length); // debug

	}

	// -------------Heap Sort ------------------------

	void heapsort(int * arr, int length)
	{
	int last_node;

	makeupheap(arr, length); // made top-heavy heap ,top node is the largetst value arr[0]

	printf("before heapsort lens=%d \n",length); // debug

	for(last_node = length-1; last_node > 0; last_node--)
	{
	/* 1. swap the largest value [0] and last node, extract top-node
	2. make new heap except last node (direction : down)
	last_node means length and last_node
	3. repeat 1,2 */

	swap(&arr[0], &arr[last_node]);
	makeheap(arr, 0, last_node,SET_DOWNHEAP); // make heap , direction : down
	}

	printf("after heapsort lens=%d \n",length); // debug
	printarry(arr,length); // debug
	}

	// ------------------ Priority Queue --------------

	#define PQUEUE_MAX 100
	int pqueue_size=0;

	int pqueue_init(int arr[], int lens)
	{
	if( lens >= PQUEUE_MAX )
	return -1;

	makeupheap(arr,lens); //make heap , direction : up
	pqueue_size=lens;

	printf("pqueue_init: lens=%d \n",pqueue_size); // debug,

	return 0;
	}

	int pqueue_insert(int arr[], int* data)
	{

	if(pqueue_size >= PQUEUE_MAX )
	return -1;

	printf("pqueue_insert: lens=%d data=%d \n",pqueue_size,*data); // debug,

	arr[pqueue_size++]=*data; // last node
	makeupheap(arr,pqueue_size); // make heap , direction : up

	return 0;
	}

	int pqueue_extract(int arr[], int* data) // have problem, can't use top nodes arrarys
	{

	int last_node;

	last_node = pqueue_size - 1;

	swap(&arr[0], &arr[last_node]);
	makeheap(arr, 0, last_node,SET_DOWNHEAP); //make heap , direction : down
	*data = arr[last_node];

	pqueue_size=last_node;

	printf("pqueue_extract: lens=%d data=%d\n",pqueue_size,*data); // debug,

	return 0;
	}

	int main(void)
	{
	int arr1[] ={25,20,22,17,19,10,12,15,7,9,18,24};
	int arr2[PQUEUE_MAX]={25,20,22,17,19,10,12,15,7,9,18,24};
	int lens1;
	int lens2;
	int data,i;

	// input
	lens1=sizeof(arr1)/sizeof(int);
	lens2=sizeof(arr1)/sizeof(int);

	printf("origin array lens=%d \n",lens1); // debug
	printarry(arr1,lens1);

	//heapsort test
	heapsort(arr1, lens1);

	//priority queue test start
	pqueue_init(arr2,lens1); // now, same size is lens1 with lens2

	for(i=0;i< 10; i++) // everytime check queue insert and extract
	{
	data= i* 5+3 ; // test value,
	pqueue_insert(arr2,&data);
	pqueue_extract(arr2,&data);
	}

	for(i=0;i< 15; i++)
	{
	data= i* 5 + 3+1 ; // test value,
	pqueue_insert(arr2,&data);
	}

	for(i=0;i< 10; i++)
	pqueue_extract(arr2,&data);

	return 0;
	}

view raw langc_algo_heap_heapsort_pqueue.c hosted with ❤ by GitHub

피드 구독하기: 글 ( Atom )