- 기본구조
여기서 간단한 한가지 특징 존재한다.
항상 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 설명
시간의 복잡도는 Insert 할 경우는 Worst Case O(LogN)이다.
1.2 Heap 기본구현 (Array 방식)
기본성질 Array Binary Tree 기본 성질 array를 0부터 사용할 경우
- Number Node
Array즉 배열을 이용하여 이진 트리를 구성해야하기 때문에 Array와 binary Tree의 성질
알아야한다.
- Array로 Binary Tree 구현할 경우 기본성질
- Left Node = 2i+1
- Right Node = 2i+2
- Parent Node = (i-1)/2
자세한 내용은 2.2 Data의 정적구현 참조
- 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)
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 예제
이해가며, 그냥 내가 다시 구현했다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
; Using a constant-size 
![{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40715162d91a34daf9bcfed5f41d8e336417f803)
