#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include
<iomanip.h>
#include<time.h>
#define
REMOVE -200
//*************************CLASS
HEAP_CLASS**********************************
class
HeapClass
{
public:
HeapClass(int IntArray[], int Count);
HeapClass(int
MAXSIZE);
int Delete(void);
void Insert(int Item);
int FindMax();
int FindMin();
bool IsEmpty() ////IS EMPTY FUNCTION
{
return HeapSize == 0;//inline function
}
void SORT(int IntAarray[], int MAX);
void Remove( int item);
private:
int * HeapArrayPtr; // pointer to array holding the heap data
int MaxHeapSize;
int HeapSize;
void FilterDown(int StartIndex);
void FilterUp(int StartIndex);
int Parent(int CurrentIndex)
{
return (CurrentIndex - 1) / 2;
}
int RightChild(int CurrentIndex)
{
return 2 * (CurrentIndex + 1);
}
int LeftChild(int CurrentIndex)
{
return 2 * CurrentIndex + 1;
}
};
//*************************consrurctor()***************************************
HeapClass::HeapClass(int
MAXSIZE)
{
int
*HeapArrayPtr = new int [] ;
MaxHeapSize
= MAXSIZE;
HeapSize=0;
}
//***************************constructor()******************************
HeapClass::HeapClass(int
IntArray[], int Count)
{
int
CurrentPosition;
if (Count <= 0)
{
cerr << "Cannot construct a
heap with size 0 or less." << endl;
exit(1);
}
MaxHeapSize = Count;
HeapSize = Count;
HeapArrayPtr = IntArray;
// a pointer assignment statement
// Set CurrentPosition to the last index of
a parent node:
CurrentPosition = (HeapSize - 2) / 2;
while (CurrentPosition >= 0)
{
// Get heap condition for subtree rooted
at index CurrentPosition:
FilterDown(CurrentPosition);
CurrentPosition--;
}
}
//*****************************DELETE()*********************************
/*
Given: Nothing other than the implicit
HeapClass object.
Task:
To remove the smallest item from the heap and readjust it
so that it remains a heap. If there is nothing to remove
from the heap, terminate the
program.
Return: In the function name, return this
smallest item.
*/
int HeapClass::Delete(void)
{
int Temp;
if (HeapSize == 0)
{
cerr << "Cannot remove from
an empty heap" << endl;
exit(1);
}
Temp = HeapArrayPtr[0]; // Item at index 0 is the smallest
// copy last one to root:
HeapArrayPtr[0] = HeapArrayPtr[HeapSize -
1];
HeapSize--;
FilterDown(0); // readjust to be a heap
return Temp;
}
//**************************FILTER
DOWN()************************************
/*
Given: StartIndex Index at which to start restoring the heap.
Of course, we also have the implied
HeapClass object.
It is assumed that we already have
a heap except possibly
for the item at index StartIndex.
Task:
To readjust the items in the subtree rooted at StartIndex
so that we have a heap.
Return: Nothing directly, but the implied
HeapClass object is
modified.
*/
void
HeapClass::FilterDown(int StartIndex)
{
int CurrentPosition, ChildPosition,
RightChildPosition, Target;
CurrentPosition = StartIndex;
Target = HeapArrayPtr[StartIndex];
ChildPosition = LeftChild(CurrentPosition);
while (ChildPosition < HeapSize)
{
RightChildPosition = ChildPosition + 1;
// Set ChildPosition to index of
smaller of right, left children:
if ((RightChildPosition < HeapSize)
&&
(HeapArrayPtr[RightChildPosition]
<= HeapArrayPtr[ChildPosition]))
ChildPosition = RightChildPosition;
if (Target <=
HeapArrayPtr[ChildPosition])
break; // Get out of loop, heap OK with Target at CurrentPosition
// Move value of the smaller child to
the parent node:
HeapArrayPtr[CurrentPosition] =
HeapArrayPtr[ChildPosition];
// Move down the tree:
CurrentPosition = ChildPosition;
ChildPosition =
LeftChild(CurrentPosition);
}
// Put Target into the correct location:
HeapArrayPtr[CurrentPosition] = Target;
}
//**************************FILTER
UP()**********************************
/*
Given: StartIndex The index at which to start restoring the
heap.
Of course, we also have the implied
HeapClass object.
It is assumed that we have a heap
from index 0 to index
StartIndex - 1, so that the only
item possibly out of order
is the one at StartIndex.
Task:
Move up the tree from StartIndex, adjusting so as to
have a heap from index 0 to index
StartIndex.
Return: Nothing directly, but the implied
HeapClass object is
modified.
*/
void
HeapClass::FilterUp(int StartIndex)
{
int CurrentPosition, ParentPosition,
Target;
CurrentPosition = StartIndex;
ParentPosition = Parent(CurrentPosition);
Target = HeapArrayPtr[StartIndex];
while (CurrentPosition != 0)
{
if (HeapArrayPtr[ParentPosition] <=
Target)
break; // Get out of loop, heap OK
with Target at CurrentPosition
// Move parent value to child:
HeapArrayPtr[CurrentPosition] =
HeapArrayPtr[ParentPosition];
// Move up in the tree:
CurrentPosition = ParentPosition;
ParentPosition =
Parent(CurrentPosition);
}
// Place Target at the position located for
it:
HeapArrayPtr[CurrentPosition] = Target;
}
//**********************INSERT()**************************************
/*
Given: Item Number to insert into the heap.
Of course, we also have the implied
HeapClass object.
Task:
To insert Item into the heap so as to maintain it as a heap.
Return: Nothing directly, but the implied
HeapClass object is modified.
*/
void
HeapClass::Insert(int Item)
{
if (HeapSize == MaxHeapSize)
{
cerr << "Cannot insert into a
full heap" << endl;
exit(1);
}
// At first, place item at the end of the
heap:
HeapArrayPtr[HeapSize] = Item;
FilterUp(HeapSize); // restore heap property
HeapSize++;
}
//************************SORT()**************************************
/*
GIVEN:
A HEAPYFIES ARRAY TO
TASK: TO SORT THE ARRAY IN THE ASCENDING ORDER
RETURN:
Nothing directly, but the implied HeapClass object is modified.
*/
void
HeapClass::SORT(int IntArray[], int MAX)
{
int Smallest, a;
HeapClass (IntArray, MAX); // constructor makes IntArray a heap
for (a = MAX - 1; a >= 1; a--)
{
// Remove smallest item and place at
index k
Smallest = Delete();
IntArray[a] = Smallest;
}
// At this point IntArray[0] contains the
largest item by default
cout<<"print
data in descending order"<<endl;
for (int k = 0; k <MAX; k++)
{
cout << setw(10) <<
IntArray[k];
}
cout << endl;
}
//*****************************FindMin()**********************************
int
HeapClass::FindMin()
{
int Temp;
if (HeapSize == 0)
{
cerr << "empty heap"
<< endl;
exit(1);
}
return
Temp = HeapArrayPtr[0]; // Item
at index 0 is the smallest
}
//*************************FINDMax()**********************************
int
HeapClass::FindMax()
{
int
temp1;
//int
temp2;
temp1=HeapArrayPtr[0];
if
(HeapSize == 0)
{
cerr << "empty heap" <<
endl;
exit(1);
}
for(int
i=1; i<MaxHeapSize; i++)
{
if(temp1<HeapArrayPtr[i])
{
temp1=HeapArrayPtr[i];
}
}
return
temp1;
}
//****************************Remove()*********************************
/*
IN
REMOVE FUNCTION THE ELEMENT TO BE ROMOVED IS SEARCHED BY LENEAR
SEARCH
IN THE ARRAY AND IF FOUND IS REPLACED BY THE LAST ELEMNT OF
THE
ARRAY. THE HEAP PROPERTY IS MAINTAINED BY CALLING THE HEAPCLASS
CONSTUCTOR
AGAIN.
*/
void
HeapClass::Remove(int item)
{
for(int
i=0; i<MaxHeapSize; i++)
{
if(HeapArrayPtr[i]==item)
{
//
HeapArrayPtr[i] = HeapArrayPtr[HeapSize - 1];
HeapArrayPtr[i]
= HeapArrayPtr[HeapSize - 1];
// HeapSize--;
}
}
HeapClass(HeapArrayPtr, MaxHeapSize-1);
}
#include"prelab10.h"
int main()
{
HeapClass H(4);
cout<<H.IsEmpty()<<endl;
H.Insert(85);
H.Insert(40);
cout<<H.Delete()<<endl;
int a[ ]={15,10,30,20};
HeapClass k(a,4);
// cout<<k.IsEmpty()<<endl;
cout<<"printing heap"<<endl;
for (int l = 0; l <4; l++)
{
cout << setw(10) << a[l];
}
cout<< endl;
cout<<k.FindMin()<<endl;
cout<<k.FindMax()<<endl;
//k.SORT(a, 4);
//cout<<k.FindMin()<<endl;
//cout<<k.FindMax()<<endl;
cout<<endl;
//cout<<k.Delete()<<endl;
//cout<<k.Delete()<<endl;
//cout<<k.Delete()<<endl;
cout<<k.Delete()<<endl;
k.Remove(15);
for ( l = 0; l <4; l++)
{
cout << setw(10) << a[l];
}
cout<< endl;
cout<<"inserting in to a new array"<<endl;
cout<<"insert"<<1<<endl;
cout<<"insert"<<2<<endl;
cout<<"insert"<<3<<endl;
HeapClass y(3);
y.Insert(1);
y.Insert(2);
y.Insert(3);
cout<<y.Delete()<<endl;
return 0;
}