Heap 과 Heap sort 와 Priority Queue

1. Heap 이란? 

• 기본구조

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

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

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

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

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

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

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

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

• Heap의 기본특성

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

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

1. Node 추가 할 경우,Child node가 추가되는 방향은 항상 왼쪽에서 오른쪽. 
2. Node 삭제 or 추가된 경우 Child node가 한개가 될 경우 left node 우선순위가 있음
3. 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 구현할 경우 기본성질  

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

 

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

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

  http://ahyuo.blogspot.kr/2016/10/tree.html

• top-heavy heap 구현방법 

1. top-heavy heap는 top node는 가장 큰 값을 소유하고 있다. 
2. Heap의 Length을 정확히 파악하여 last node의 parent와 child 대소 관계를 비교
3. Child가 큰 경우에만 Parent와 Child 교환진행 
4. 왼쪽 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 최소 값을 추출하는 방법을 이용한다.

• 구현방법 

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

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

1. top-node가 현재 작은값이기때문에 child 중 두번째로 큰 값을 찾아 교환 
2. 원래 top-node의 값은 child (left or right) 되었기에 관련 Tree는 비교 및 교환진행  
3. 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 구현방법 (정적으로 구현방법)

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

• 구현함수

1. pqueue_init : 상위 heap 구성과 동일 
2. pqueue_insert :  pqueue_init와 동일 
3. 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 기반으로,
이해가며, 그냥 내가 다시 구현했다.