Heap Sort

We can use heaps to sort. 

void heapsort( vector<int> & data )
{
  unsigned int N = data.size()-1;	// Can't use zero slot.

  Build_Heap( data , 1 );

  for( unsigned int i = 0; i < N; i++ )
    data[N-i+1] = Extract_Min( data );

}

Running Time? How is this nicer than merge sort? Quicksort?

\epsfig {file=figs08/qsort.ps,height=3.5in}

next up previous
Next: LISTING LARGEST ELEMENTS Up: HEAPS Previous: Insert