C++ classes: Priority Queue Minimum Heap

____________________________________

First: Header file.h (functions prototype).

____________________________________ 

// File: PQ.h
// Priority Queue header file (Minimum Heap)
/* ______________________________________________________________________________
The PQ is implemented as a minimum Heap.
The elements of the heap are of type (E).
The top of the heap will contain the smallest element.
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 for a value "itemMin" smaller
than any possible value (e.g. a negative number)
_________________________________________________________________________________
*/

#ifndef PQ_H
#define PQ_H

template <class E>

class PQ
{
  public:

    // Class Constructor with input size parameter
    PQ(int );
    // Class Destructor
    ~PQ();
    // Member Functions
    void insert(E );    // insert element into heap
    E remove();            // remove & return the top of the heap
    void dispHeap();    // Display Heap Array as a tree

   private:
    // Pointer to Storage Array
    E *a;
    // Maximum Size (not including a[0])
    int MaxSize;
    int N;                    // index of last element in the array
    E itemMin;                // itemMin to be stored in a[0]
    // Heap Adjustment Functions
    void upheap(int k);
    void downheap(int k);
    void disp_Level (int Nrows, int level, int s, int e);

};
#endif // PQ_H
#include "PQ.cpp"

________________________________________________ 

second: Implementation file.cpp 

_____________________________________

  

// File:PQ.cpp
// PQ (min Heap) Class implementation
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;


// Member Functions

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

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

template <class E>
void PQ<E>::upheap(int k)           
{
    E v = a[k] ;  
    while ( a[k/2] >= v)              
        { a[k] = a[k/2] ;   k = k/2 ; }
    a[k] = v ;
}


// downheap element at (k) in the heap
template <class E>
void PQ<E>::downheap(int k)           
{
    int j = 2 * k ;     E v = a[k] ;
    while (j <= N) {
        if ((j < N) && (a[j] > a[j+1])) j++ ;
        if ( v <= a[j] ) break;              
        a[j/2] = a[j] ;     j *= 2 ;   }
    a[j/2] = v ;
}

// Insert element (v) in the heap and adjust heap
template <class E>
void PQ<E>::insert(E v)
{
    a[++N] = v ;    upheap(N) ;
}


// remove and return top of the heap, then adjust heap
template <class E>
E PQ<E>::remove()                           
{
    E v = a[1] ;
    a[1] = a[N--] ; downheap(1) ;
    return v;
}

template <class E>
void PQ<E>::dispHeap()
{
    int s = 1, e = 1, rlength, k,
        Nlevels = int(ceil(log(float(N))/log(2.0)+ 0.01));
    for (int level=0; level<Nlevels; level++)
    {
        disp_Level (Nlevels, level, s, e);
        rlength = e-s+1;
        s = e+1;
        k = e + 2*rlength;
        e = (k < N)? k : N;
    }
}


template <class E>
void PQ<E>::disp_Level (int Nrows, int level, int s, int e)
{
    int skip = int(pow(2.0, Nrows-level) - 1);
    for (int i = s; i <= e; i++)
    {
        cout << setw(skip) << " ";
        cout << setw(2) << a[i];
        cout << setw(skip) << " ";
    }
    cout << "\n\n\n";
}

________________________________________________ 

finally class test

_____________________________________

// FILE: HeapSortTest.cpp
// Heap Sorting of a random sequence of integers.
#include "PQ.h"
#include <time.h>
#include <conio.h>
#include <iostream>
using namespace std;

// ______________________________Globals __________________
const int Nmax = 200;        // Maximum number of elements

// Functions Prototype Definitions_________________________

// Swap element[i] with element[k]
void swap(int &, int &);
// Generate a random integer from (i) to (j)
int  RandInt(int i,int j);
// Generate a random permutaion of the first N integers          
void RandPerm(int X[], int N);
// Heapsort array X[] locations 1..N       
void heapsort(int X[], int N);      

//__________________________________________________________

int main()
{
    int X[Nmax+1];    // Array of random permutation of integers
    int i,N;
    cout<<"Input N: "; cin >> N;
    srand((unsigned)time(NULL));
    RandPerm(X,N);
    for(i=1; i<=N; i++) cout<<X[i] <<" ";
    cout<<endl;
    heapsort(X,N);
    for(i=1; i<=N; i++) cout<<X[i] <<" ";
    cout<<endl;
    _getch();
    return 0;
}

//Implementation of Functions________________________________
void swap(int &a, int &b)
{
    int t;
    t = a; a = b; b = t;
}

//____________________________________________________________
int RandInt(int i,int j)                   
{
    return (rand()%(j-i+1) + i);
}
//____________________________________________________________
void RandPerm(int X[], int s)               
{
    int i,k;
    for(i=1;i<=s;i++) X[i] = i;
    for(i=2;i<=s;i++)
    {
        k = RandInt(1,i);
        swap(X[i],X[k]);
    }
}

//______________________________________________________________
void heapsort(int X[], int N)   
{
    int i;
    PQ<int> Heap(N);
    for (i = 1; i <= N; i++) Heap.insert(X[i]);
    for (i = 1; i <= N; i++) X[i] = Heap.remove();
}