// Heap.cpp
// Author : Saket Soni
// Dated : 02-10-04
// Note : Class Assignment for Data & File Structures (MTech 1st Year)
// Platform : Win 98, Visual C++ 6.0
/////////////////////////////////
//
// Header Files
//
/////////////////////////////////
#include
using namespace std;
#include
#include
#include
#include
////////////////////////////////
//
// Macros and Constant Declarions
//
////////////////////////////////
//#define OUTPUT // to enable or disable output generation
const int FIELD_WIDTH = 4; // specifies the width of the field into which the
// output will be printed
const int MaxArr = 10; // max size of array used to build heap
/////////////////////////////////
//
// Global Function Declarations
//
/////////////////////////////////
void Swap(int &, int&); // to swap to integers
int menu(); // to display a menu to the user and
// read his option
/////////////////////////////////
//
// Declaration of class CMaxHeap
//
/////////////////////////////////
class CMaxHeap // class to manage heaps
{
private:
int *heap; // pointer to array of elements
int last; // index of last element in the heap
int MAX; // max elements allowed in the heap
private:
int status; // status of the heap
// 1 - no array to work with
// 2 - array present but elements in the array do not form a heap
// 3 - array present and elements in the array form a heap
// 4 - array present and elements are sorted
private:
void preorder(int=0); // for preorder traversal of heap
void inorder(int=0); // for inorder traversal of heap
void postorder(int=0); // for postorder traversal of heap
public:
CMaxHeap():heap(NULL),last(-1),MAX(-1),status(1) { };
// creates new heap object with no array
CMaxHeap(int *arr, int max):heap(arr),last(-1),MAX(max),status(3) { }
// creates new heap and assign it an empty array of max elements
CMaxHeap(int *arr,int l, int max):heap(arr),last(l),MAX(max),status(2) { }
// creates new heap and assign it an array of max elements out
// of which l elements are already present in the array
public:
void showHeap(); // to display the contents of the array. Its behavior
// depends on the status of the heap ...
// 1 - error message is printed
// 2 - array is printed
// 3 - the preorder, inorder & postorder traversals of
// the heap are printed
// 4 - sorted array is printed
int InsertHeap(int); // to InsertHeap an element into the heap. It works only
// when current status is 3. The resultant status is 3.
int DelMaxHeap(int&); // to InsertHeap an element into the heap. It works only
// when current status is 3. The resultant status is 3.
int Sort(); // to sort the element of the heap. It is possible only if
// the current status is 2 or 3. The resultant status is 4.
int Heapify(); // to form a heap out of elements. It is possible only if
// the current status is 2 or 4. The resultant status is 3.
public:
// to allocate the heap object to another array of elements.
void setHeap(int *arr, int l, int max) {
heap = arr; last = l; MAX = max; status = 2;
}
// to remove the connection between the array of elements
void newHeap() { // and the heap object
heap = NULL; last = -1; MAX = -1; status = 1;
}
int getStatus() { // to retrieve the status of the heap
return status;
}
};
/////////////////////////////////
//
// Defination of Functions
//
/////////////////////////////////
// to swap to integers
void Swap(int & a, int & b) {
int t = a;
a = b; b = t;
}
// to sort the array
int CMaxHeap::Sort()
{
if ( status != 2 && status != 3 ) // if not an array or heap
return 0; // return false
if ( status == 2 ) // if array is not already a heap
Heapify(); // then first heapify
int lastEle = last, temp; // delete all elements from the heap
while ( DelMaxHeap(temp) ) { // one by one and place at the last
heap[last+1] = temp; // of the heap
}
last = lastEle;
status = 4; // final status is sorted
return 1; // return true
}
// to heapify an array
int CMaxHeap::Heapify()
{
if ( status != 2 && status != 4 ) // if not an array or alreay sorted
return 0; // return false
int lastEle = last;
last = -1;
while ( last < lastEle ) // take out nth element of the
InsertHeap(last+1); // array and insert it into the
// heap of n-1 elements
status = 3; // final status is a heap
return 1; // return true
}
// to display the heap/array. Its behaviour depends upon the status.
void CMaxHeap::showHeap()
{
switch ( status )
{
case 1: // if heap object has not been
cout << "Error : No array for heap!" << endl; // an array to work with
break;
case 2: // in case of unsorted
case 4: // or sorted array
cout << "The array is ..." << endl; {
for ( int k = 0 ; k <= last ; k++ )
cout << setw(FIELD_WIDTH) << heap[k];
}
cout << endl;
break;
case 3: // in case of a heap
cout << "The heap is ..." << endl;
if ( last < 0 ) {
cout << "Empty !" << endl;
return;
}
else {
cout << "preorder : \n"; preorder(); cout << endl;
cout << "inorder : \n"; inorder(); cout << endl;
cout << "postorder : \n"; postorder(); cout << endl;
cout << "array : \n";
for ( int k = 0 ; k <= last ; k++ )
cout << setw(FIELD_WIDTH) << heap[k];
cout << endl;
}
break;
};
}
// to traverse in preorder and print elements
void CMaxHeap::preorder( int l ) {
if ( l > last )
return;
cout << setw(FIELD_WIDTH) << heap[l];
preorder(2*l+1);
preorder(2*l+2);
}
// to traverse in inorder and print elements
void CMaxHeap::inorder( int l ) {
if ( l > last )
return;
inorder(2*l+1);
cout << setw(FIELD_WIDTH) << heap[l];
inorder(2*l+2);
}
// to traverse in postorder and print elements
void CMaxHeap::postorder( int l ) {
if ( l > last )
return;
postorder(2*l+1);
postorder(2*l+2);
cout << setw(FIELD_WIDTH) << heap[l];
}
// to insert an element into the heap
int CMaxHeap::InsertHeap( int item )
{
if ( status != 3 ) // if array is not an heap
return 0; // then return false
if ( (last+1) == MAX ) // if heap is full
return 0; // then return false
int l = last+1, f = last/2; // to make place for the
while ( l > 0 && heap[f] < item ) { // new element
heap[l] = heap[f];
l = f;
f = (l-1)/2;
}
if ( l == f ) // this means that the element
heap[0] = item; // has to be inserted at the root
else
heap[l] = item; // else element goes into the
last++; // heap at location l
return 1; // return true
}
// to delete an element from the heap
int CMaxHeap::DelMaxHeap( int &item )
{
if ( status != 3 ) // if array is not an heap
return 0; // then return false
if ( last == -1 ) // if heap is empty
return 0; // then return false
item = heap[0]; // delete top
int p = 1; // to fill the vacant space
while ( p < last ) { // created at the root in
if ( heap[p] < heap[p+1] ) // such a way that the resultant
p = p+1; // is still a heap
if ( heap[p] > heap[last] ) {
Swap(heap[p],heap[(p-1)/2]);
p = p*2+1;
}
else
break;
}
heap[(p-1)/2] = heap[last];
last--;
return 1; // return true
}
// to display a menu to the user and to read his option
int menu()
{
cout << "Menu : " << endl // display menu
<< "1. Insert one element" << endl
<< "2. Delete maximum element" << endl
<< "3. Insert elements randomly" << endl
<< "4. Delete first k maximum elements" << endl
<< "5. Exit" << endl
<< "Enter your option (1-5) : ";
int opt = 0;
cin >> opt; // read option
if ( cin.fail() ) // for typographical errors
cin.clear();
while ( cin.get() != '\n' );
#ifdef OUTPUT
cout << opt << endl;
#endif
return opt; // return read option
}
////////////////////////////////
//
// Application Entry point
//
////////////////////////////////
void main()
{
int Arr[MaxArr]; // array to be used for heap
CMaxHeap h(Arr,MaxArr); // heap object with array Arr
// as the heap array
int v,k,n; // local variables
srand( (unsigned) time(NULL)); // seed the random number
// generator
while ( 1 )
{
switch( menu() )
{
case 1:
// read value less than 1000 this conditon is just to ensure
// proper display of data on the screen
cout << "Enter value to enter ( |val| < 1000 ): ";
cin >> v;
if ( cin.fail() ) { // for typographical errors
cin.clear();
while ( cin.get() != '\n' );
cout << "Incorrect Entry !" << endl;
break;
}
while ( cin.get() != '\n' );
#ifdef OUTPUT
cout << v << endl;
#endif
if ( v >= 1000 || v <= -1000 ) { // check for |val| < 1000
cout << "Incorrect Entry !" << endl;
}
else if ( !h.InsertHeap(v) ) // insert element if |val| ok
cout << "ERROR : Cannot Insert, Heap is Full !" << endl;
break;
case 2:
if ( h.DelMaxHeap(v) ) // delete element from heap
cout << "Deleted Element is : " << v << endl;
else // if unable to delete show error
cout << "ERROR : Cannot Delete, Heap is Empty !" << endl;
break;
case 3:
// read the number of elements to be insert randomly
cout << "Enter number of elements to enter randomly : ";
cin >> n;
if ( cin.fail() ) { // for typographical errors
cin.clear();
while ( cin.get() != '\n' );
break;
}
while ( cin.get() != '\n' );
#ifdef OUTPUT
cout << n << endl;
#endif
cout << "Randomly inserted elements are : " << endl;
for ( k = 0 ; k < n ; k++ )
{
v = int( rand() * 1000.0 / RAND_MAX ); // generate random number
if ( !h.InsertHeap(v) ) // insert the number and if
{ // error then show error
if ( k )
cout << endl
<< "ERROR : Cannot Insert further, Heap is Full !" << endl;
else
cout << "ERROR : Cannot Insert, Heap is Full !" << endl;
cout << k << " elements inserted";
break;
}
else
cout << setw(FIELD_WIDTH) << v; // display the inserted number
}
cout << endl;
break;
case 4:
// read the number of elements to be deleted
cout << "Enter number of elements to delete : ";
cin >> n;
if ( cin.fail() ) { // for typographical errrors
cin.clear();
while ( cin.get() != '\n' );
break;
}
while ( cin.get() != '\n' );
#ifdef OUTPUT
cout << n << endl;
#endif
cout << "Deleted elements are : " << endl;
for ( k = 0 ; k < n ; k++ )
{
if ( !h.DelMaxHeap(v) ) // delete max element and
{ // if empty then show error
if ( k )
cout << endl
<< "ERROR : Cannot Delete further, Heap is Empty !" << endl;
else
cout << "ERROR : Cannot Delete, Heap is Empty !" << endl;
cout << k << " elements deleted";
break;
}
cout << setw(FIELD_WIDTH) << v;
}
cout << endl;
break;
case 5: // exit from program
return;
default:
cout << "Incorrect Entry !" << endl; // incorrect option selected
}
h.showHeap(); // diaplay heap
cout << endl;
}
}