/**
* Remove the smallest item from the priority queue
* and place it in minItem. Throw Underflow if empty.
*/
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw Underflow( );
/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
/**
* Test if the priority queue is logically empty.
* Return true if empty, false otherwise.
*/
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
return currentSize == 0;
}
/**
* Test if the priority queue is logically full.
* Return true if full, false otherwise.
*/
template <class Comparable>
bool BinaryHeap<Comparable>::isFull( ) const
{
return currentSize == array.size( ) - 1;
}
/**
* Make the priority queue logically empty.
*/
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
currentSize = 0;
}
/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
/* 1*/ int child;
/* 2*/ Comparable tmp = array[ hole ];
// HeapSort with ButtomUpHeap construction O(n + n*log(n)) = O(n*log(n))
// =======================================
public static void heapSort(Comparable[] V)
{
int n = V.length - 1;
Comparable[] T = new Comparable[V.length + 1];
for (int i = 0; i < V.length; i++) T[i + 1] = V ;
n = T.length - 1;
for (int i = n / 2; i > 0; i--) DownHeapBubbling(T, i, n);
for (int i = n; i > 1; i--)
{
swap(T, 1, i);
DownHeapBubbling(T, 1, i - 1);
}
for (int i = 0; i < V.length; i++) V = T[i + 1];
return;
}
public static void DownHeapBubbling(Comparable[] V, int i, int n)
{
int left = 2 * i;
int right = 2 * i + 1;
int high;
if (left <= n && V[left].compareTo(V ) > 0) high = left;
else high = i;
if (right <= n && V[right].compareTo(V[high]) > 0) high = right;
if (high != i)
{
swap(V, i, high);
DownHeapBubbling(V, high, n);
}
return;
}