[Algorithm]힙(Heap)+ 우선순위Q

1. 히프(Heap)

   a. 정의: 각 노드의 키 값이 자식의 키 값보다 작지않은 완전 이진트리이다.

   b. 종류: 최대 히프(Max heap) - 각 노드의 키 값 > 그 자식 키 값

                최소 히프(Min heap) - 각 노드의 키 값 < 그 자식 키 값

   c. 특징: 최소 히프의 루트 = 트리에서 가장 작은 키 값, 최대 히프의 루트 = 트리에서 가장 큰 키 값

   d. 연산 알고리즘:

H ∈ Heap; e ∈ Element;
createHeap() := create an empty heap; //공백 히프 생성 
insertHeap(H, e) := insert a new item e into H // 새로운 원소를 히프에 삽입
isEmpty(H) := if the heap H is empty
			  then return true
              else return false
deleteHeap(H) := if isEmpty(H) then null
				else{
                	e <- the largest element in H;
                    remove the largest element in H;
                    return e;
                }

원소 삽입과정

   e. 부모노드 위치 결정 방법이 중요

      - 순차표현 사용: 위치 i의 부모 노드는 [i/2]에 위치함

      - 연결표현 사용: 각 노드에 parent 필드 추가

insertHeap(head, item)
	if(n==heapSize) then heapFull; // 히프가 만원이면 크기를 확장
    n <- n+1;		// 추가 될 노드 위치
    for(i<-n;;) do{
    	if(j==1) then exit;
        if(item <= heap[i/2]) then exit;
        heap[i] <- heap[i/2];
        i <- i/2;
       }
    heap[i] <- item;

    - 자바로 알고리즘 구현

void insertHeap(int heap[],int k){
   int i;
   n++;
   for(i = n; ; ){
      if(i == 1) break;
      if(k<=heap[i/2]) break;
      heap[i] = heap[i/2];
      i = i/2;
   }    
   heap[i]=k;
}

3. 히프에서의 삭제

  - 히프의 최대 원소가 루트에서 가장 큰 원소를 갖기 때문에 루트 원소를 삭제함을 의미한다.

  - 마지막 원소 루트에 위치 시킨 뒤 -> 나머지 트리 재조정

  - 삭제 알고리즘

deleteHeap(heap)
	if(n==0) then return error; // 공백
    item <- heap[1];	// 삭제할 원소
    temp <- heap[n];    // 이동시킬 원소
    n <- n-1;			// 히프 크기 하나 감소
    i <- 1;
    j <- 2;				// i의 왼쪽 자식 노드
    while(j<=n) do{
    	if(j<n) then 
        	if(heap[j]<heap[j+1]) then j <- j+1;
        if(temp>=head[j]) then exit;
        heap[i] <- heap[j] // 자식을 한 레벨 위로 이동
        i <- j;
        j <- j * 2;		// j와 i를 한 레벨 아래로 이동
    }
    heap[i] <- temp;
    return item;

    - 자바로 알고리즘 구현

int delete(int heap[]){
   int temp = heap[n];
   int del = heap[1];
   int i = 1;
   int j = 2;
   heap[n] = 0;
   n--;

   while(j <= n){
      if(j < n){
         if(heap[j]<heap[j+1]) j++;
      }
      if(temp > heap[j]) break;
      heap[i]=heap[j];
      i=j;
      j *= 2 ;
   }
   heap[i]=temp;
   return del;
}

3. 완전 이진트리를 히프로 변환

    - 초기 히프로 되어있지 않은 완전 이진 트리 H를 히프로 변환(역 레벨 순서로 히프로 만듦)

    - 알고리즘

makeTreeHeap(H, n)
	for(i <- n/2; i>=1; i<- i-1) do{ // 각 내부 노드에 대해 레벨 순서 역으로
    	p <- i; 	
        for(j <- 2*p; j<=n; j<-2*j) do {
        	if(j<n) then
            	if(H[j] < H[j+1]) then j <- j+1;
            if(H[p] >= H[j]) exit;
            temp <- H[p];
            H[p] <- H[j];
            H[j] <- temp;
            p <- j;  		// 부모 노드를 한 레벨 밑으로 이동
        }
    }

    - 자바로 알고리즘 구현

void make_Tree_Heap(int stree[])
{
   //완전이진트리를 히프로 변환
   int num = stree.length-1;
   for(int i = num/2; i >= 1; i--)
   {
      int p = i;
      for(int j=2*p; j<=n; j*=2)
      {
         if (j < num) {
            if (stree[j] < stree[j+1]) j=j+1;
         }
         if(stree[p]>=stree[j]) break;
         int temp = stree[p];
         stree[p]=stree[j];
         stree[j]=temp;
         p =j;
         
      } // end of for
   } // end of outer for 
} // end of makeTreeHeap