7. 최대 히프 (Max Heap)

dyeoma.tistory.com/18

최대 히프

 

 

최대 히프 class

class MaxHeap {
   ...
private:
   Element<Type> *heap;
   int n;		// 히프 현재 크기
   int MaxSize;		// 히프 최대 크기
}

 

최대 히프 생성자

MaxHeap::MaxHeap (int size=DefaultSize){
   MaxSize = size; n=0;
   heap = new Element<Type>[MaxSize + 1];	// heap[0]은 미사용
}

 

 

최대 히프 삽입 함수 - O(log_2(n)) 소요  [ log_2(n) = 완전이진트리 높이 ]

template <class Type>
void MaxHeap<Type>::Insert(const Element<Type> &x){
   int i;
   if (n==MaxSize) {	// full이면 크기 확장
      HeapFull();
      return;
   }
   n++;
   
   for(i=n; 1; ){
      if(i==1)	// root node
         break;
      if(x.key <= heap[i/2].key)
         break;
         
      // parent -> child
      heap[i] = heap[i/2];
      i/=2;      
   }
   heap[i] = x;
}

 

 

최대 히프 삭제 함수 - O(log_2(n)) 소요  [ log_2(n) = 완전이진트리 높이 ]

template <class Type>
Element<Type> *MaxHeap<Type>::DeleteMax (Element<Type> &x){
// 최대히프 삭제
   int i;
   
   if(!n)	// empty heap
      return 0;
   
   x = heap[1];
   Element<Type> k = heap[n];
   n--;
   
   for (i=1, int j=2; j<=n; ){
      
      // j는 값이 더 큰 child
      if (j<n)
         if (heap[j].key < heap[j+1].key)
            j++;
      
      if(k.key >= heap[j].key)
         break;
         
      // child를 parent로 이동
      heap[i] = heap[j];
      // i,j child로 이동
      i=j; j*=2;      
   }
   heap[i]=k;
   return &x;   
}