C++ classes: Minimum Heap

____________________________________

First: Header file.h (functions prototype).

____________________________________ 

// File: MinHeap.h
// Heap Class header file (Minimum Heap for graph edges)
/* ________________________________________________________________________________________________
The following is a definition of a class for a Minimum Heap "MinHeap". The elements of the heap are
structs that model an edge in a non-directed weighted graph. Each edge is characterized by three
integers: (u,v,w). u is the index of a node, v is the index of the second node, and w is the weight
of the edge between u and v. The top of the heap will contain the edge with the minimum weight. The
heap condition is that a parent is always less than or equal to the children. The heap is implemented
as a dynamic array a[] with a size specified by the class constructor. Location a[0] is reserved to
contain a weight value "itemMin" smaller than any possible weight value (e.g. a negative number)
___________________________________________________________________________________________________
*/

#ifndef MINHEAP_H
#define MINHEAP_H
#include "Edge.h"
using namespace std;


class MinHeap
{
  public:
   
      // Member Functions
    // Class Constructor with input size parameter
    MinHeap(int );
    // Class Destructor
    ~MinHeap();
    // Functions Prototype Definitions
    void insert(Edge e);            // insert edge into heap
    Edge remove();        // remove the top of the heap
   private:
    // Pointer to Storage Array
    Edge *a;
    // Maximum Size (not including a[0])
    int MaxSize;
    int N;                            // index of last element in the heap
    weightType itemMin;                // itemMin to be stored in a[0]
    // Heap Adjustment Functions
    void upheap(int k);
    void downheap(int k);

};
#endif // MINHEAP_H
#include "MinHeap.cpp"



________________________________________________ 

second: Implementation file.cpp 

_____________________________________

// File:MinHeap.cpp
// Heape Class implementation file (Minimum heap for graph edges)


// Member Functions

// Constructor with argument. max size is mVal elements
// not including a[0] which will receive a weight -32767
// The constructor creates the heap array, initializes
// the end of the heap to N=0,and itmMin
MinHeap::MinHeap(int mVal)
{
    a = new Edge[mVal+1];     N=0;
    MaxSize = mVal; itemMin = -32767; // Minimum Heap
    a[0].w = itemMin ;
}
// Class Destructor
MinHeap::~MinHeap()
{ delete [] a;}

// Heap Adjustment Functions
// upheap element at location (k) in the heap
// as long as it is less than the parent

void MinHeap::upheap(int k)            
{
    Edge e = a[k]  ;
    while ( e <= a[k/2])               
        { a[k] = a[k/2] ;   k = k/2 ; }
    a[k] = e ;
}

// downheap element at (k) in the heap
void MinHeap::downheap(int k)            
{
    int j = 2 * k ;     Edge e = a[k] ;
    while (j <= N) {
        if ((j < N) && (a[j+1] < a[j])) j++ ;
        if ( e <= a[j] ) break;               
        a[j/2] = a[j] ;     j *= 2 ;   }
    a[j/2] = e ;
}

// Insert (e) in a heap and adjust heap
void MinHeap::insert(Edge e)                    
{
    a[++N] = e ;    upheap(N) ;
}


// remove and return top of the heap, then adjust heap
Edge MinHeap::remove()                            
{
    Edge e = a[1] ;
    a[1] = a[N--] ; downheap(1) ;
    return e;
}