Main Page   Packages   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Search  

MaxHeap Class Reference

#include <MaxHeap.hpp>

List of all members.

Public Methods

 MaxHeap (Elem *, int, int)
int heapsize () const
bool isLeaf (int) const
int leftchild (int) const
int rightchild (int) const
int parent (int) const
void insert (const Elem)
Elem removemax ()
Elem remove (int)
void buildMaxHeap ()

Private Methods

void siftdown (int)

Private Attributes

Elem * Heap
int size
int n

Constructor & Destructor Documentation

MaxHeap::MaxHeap (  Elem *    h,
int    num,
int    max
) 
 

Definition at line 7 of file MaxHeap.cpp.

00008 : Heap( h ), n( num ), size( max )
00009 {  
00010    buildMaxHeap();
00011 }

Member Function Documentation

void MaxHeap::buildMaxHeap (    ) 
 

Definition at line 110 of file MaxHeap.cpp.

Referenced by MaxHeap(). 

00111 {
00112   for ( int i = n/2 - 1; i >= 0; i--) 
00113   {
00114     siftdown(i);
00115   }
00116 }

int MaxHeap::heapsize (    )  const [inline]
 

Definition at line 14 of file MaxHeap.cpp.

00015 { 
00016    return n;
00017 }

void MaxHeap::insert (  const Elem    val ) 
 

Definition at line 60 of file MaxHeap.cpp.

00061 {
00062   if ( n < size ) return;
00063   
00064   int curr   = n++;
00065   Heap[curr] = val;        // Start at end of MaxHeap
00066 
00067   // Now sift up until curr's parent > curr
00068 
00069   while ( curr != 0  &&  Heap[curr] > Heap[ parent(curr) ] )
00070   {
00071     swap( Heap, curr, parent(curr) );
00072     curr = parent(curr);
00073   }
00074 }

bool MaxHeap::isLeaf (  int    pos )  const
 

Definition at line 20 of file MaxHeap.cpp.

Referenced by siftdown(). 

00021 { 
00022    return (pos >= (n/2))  &&  (pos < n);
00023 }

int MaxHeap::leftchild (  int    pos )  const
 

Definition at line 26 of file MaxHeap.cpp.

Referenced by siftdown(). 

00027 {
00028  //  assert( pos < (n/2) );
00029      return 2*pos + 1;  
00030 }

int MaxHeap::parent (  int    pos )  const
 

Definition at line 47 of file MaxHeap.cpp.

Referenced by insert(), and remove(). 

00048 {
00049   if ( pos > 0 ) 
00050   {
00051      return -100;          // Error Flag
00052   } 
00053   else                     // Pos must have a parent
00054   {
00055     return (pos-1)/2;
00056   }
00057 }

Elem MaxHeap::remove (  int    pos ) 
 

Definition at line 91 of file MaxHeap.cpp.

00092 {
00093   assert((pos > 0) && (pos < n));
00094   swap(Heap, pos, --n);    // Swap with last value
00095 
00096   while ( Heap[pos] > Heap[ parent(pos) ] )       // Push up
00097   {
00098     swap(Heap, pos, parent(pos));                 //  if large key
00099   }
00100 
00101   if (n != 0) 
00102   {
00103     siftdown(pos);         // Push down if small key
00104   }
00105 
00106   return Heap[n];
00107 }

Elem MaxHeap::removemax (    ) 
 

Definition at line 77 of file MaxHeap.cpp.

Referenced by HeapSort(). 

00078 {
00079   assert(n > 0);
00080   swap(Heap, 0, --n);  // Swap maximum with last value
00081 
00082   if (n != 0)          // Not on last element
00083   {
00084     siftdown(0);       // Put new MaxHeap root val in correct place
00085   }
00086 
00087   return Heap[n];
00088 }

int MaxHeap::rightchild (  int    pos )  const
 

Definition at line 33 of file MaxHeap.cpp.

00034 {
00035   if ( pos < (n-1)/2 )     // Error Flag
00036   {
00037      assert( false );
00038      return -100;          // Must be a position with a right child
00039   } 
00040   else 
00041   {
00042      return 2*pos + 2;
00043   }
00044 }

void MaxHeap::siftdown (  int    pos )  [private]
 

Definition at line 119 of file MaxHeap.cpp.

Referenced by buildMaxHeap(), remove(), and removemax(). 

00120 { 
00121   assert( (pos >= 0) && (pos < n) );
00122 
00123   while ( !isLeaf(pos) )  // Move down until current pos is a leaf
00124   {
00125     int j = leftchild( pos );
00126 
00127     if ( ( j < (n-1) )  &&  (Heap[j] < Heap[j+1]) ) 
00128     {
00129       j++; // j is now index of child with greater value
00130     }
00131 
00132     if ( Heap[pos] >= Heap[j] ) return; // Done
00133 
00134     swap(Heap, pos, j);
00135     pos = j;  // Move down
00136   }
00137 }

Member Data Documentation

Elem* MaxHeap::Heap [private]
 

Definition at line 24 of file MaxHeap.hpp.

int MaxHeap::n [private]
 

Definition at line 26 of file MaxHeap.hpp.

int MaxHeap::size [private]
 

Definition at line 25 of file MaxHeap.hpp.

The documentation for this class was generated from the following files:
Generated on Sun Oct 14 18:49:22 2001 for Standard J2K Library by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001