/* Filename: heap.cpp
Programmer: Br. David Carlson
Date: October 4, 1997
Revised: June 19, 1999
Revised: July 17, 2000 to use modern headers.
Reference: Data Structures with C++, by Ford and Topp, pp 690 - 703.
This file implements the functions for the HeapClass declared in heap.h.
*/
#include "heap.h"
/* Given: IntArray Array of integers.
Count The number of integers in IntArray.
Task: To construct a heap object containing a pointer to IntArray.
This includes moving the data around in IntArray so as to get
a heap.
Return: IntArray Modified array.
The object itself is also modified and will contain a
pointer to the array that holds the heap data.
*/
HeapClass::HeapClass(IntArrayType 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--;
}
}
/* 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;
}
/* 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;
}
/* 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;
}
/* 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++;
}