우선순위 큐

리스트 이용 ( 삽입 O(1), 삭제 O(n)) )  

힙        이용 ( O(logn)  O(logn) )

 

힙이란 ?  완전 이진 트리 의 일종

 

[힙정렬 구현 ]

#include <bits/stdc++.h>

void heapSort(vector<int> &arr){

  priority_queue<int> h;  // 가장 큰 값을 먼저 뱉게 되어있음

  for ( int i =0 ; i < arr.size(); i++){

    h.push(-arr[i]);

  }

  while (!h.empty()){

   printf(" %d\n", -h.top());

   h.pop();

  }

}

 

#include<stdio.h>

#defind MAX_N 100

 

void heapInit(void){

  heapSize = 0; 

}

int isHeapFull(){

  heapSize +1 > MAX_N

}

맨마지막에 넣고, 비교하면서 올리기

int heapPush(int value){

  if ( heapSize + 1 > MAX_N){

    return 0 ; 

  }

  heap[heapSize] = value;  // 힙 맨마지막에 넣어준다. 

 // 넣어준 것을 자리 잡아준다. (Heapify )

  int current = heapSize ;  // 배열을 이용해서 트리를 만들어 나갈것이다.

  parent = ( current -1 ) / 2 

  while ( current > 0 && heap[current]< heap [ (current-1)/2 ] ){ // 현재 위치가 0보다 크고, 부모가 나보다 크다면

      int temp = heap [ parent ] ;

      heap [ parent ] = heap [ current ] ;

      heap [current ] = ttemp ; 

       current = parent ;

      parent = ( current - 1  )/ 2

  }

  heapSize + = 1; 

}

 

int heapPop(){

    * value = heap[0];
   heap[0] = heap[heapSize];

   int current =0 ; 

   while ( current * 2 + 1 < heapSize)  // 자식이 있는동안

   { 

      int child; 

      if ( current *2 + 2 == heapSize){ 

         child = current * 2 + 1 ;

      }

    }

}