Hello, everybody! I am kind of new to the forums, and I will do my best to follow the rules when posting a new thread.
I am to create a program that is supposed to generate 30 random integers between 10 and 200, and insert them into a Heap. The Heap is then used to sort the integers in descending order by storing them in an array as they are pulled off the Heap. This is what I have so far:
Heap.h
/* --- Heap.h ------------------------------------------------------------------
A header and file for class type Heap that defines the
methods and data members that allow data of template typename ItemType to be
stored and sorted using a heap ADT.
Operations are:
Heap() : Default, zero argument constructor that initializes the
heap's size to zero.
isEmpty() : Returns a boolean "true" if the heap is empty;
otherwise, it returns false.
isFull() : Returns a boolean "true" value if the heap is full;
otherwise it returns false.
display() : Displays the heap-array in index order.
Left() : Returns the array-index position of the left child of a
given node.
Right() : Returns the array-index position of the right child of a
given node.
Parent() : Returns the array-index position of the parent of a
given node.
insert() : Inserts a value into the heap and applies the
percolateUp() function to that value to ensure it is
placed correctly within the heap.
removeMax() : Moves the heap's maximum value (it's root node) to the
end of the heap array and decreases the heap's size by
one. ReHeap() is then applied to the heap to ensure it
still maintains the heap property. Finally, the maximum
value pulled from the heap is returned.
percolateUp() : Compares the value of a given node with the value of
that node's parent and swaps them if the node's value
is greater than the parent's. This is continued
recursively until the proper position for the node is
found. [Used with insert()]
ReHeap() : Compares the value of a given node with its left and
right children and swaps the two values if a child is
greater than the parent. This is continued recursively
until the proper position for the node is found. [Used
with removeMax()]
------------------------------------------------------------------------------*/
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_SIZE = 30; // the maximum amount of elements our heap should
// have
template <class ItemType>
class Heap
{
public:
Heap();
bool isEmpty() const;
bool isFull() const;
void display() const;
int Left(int) const;
int Right(int) const;
int Parent(int) const;
void insert(const ItemType&);
ItemType removeMax();
private:
ItemType myArray[MAX_SIZE]; // Heap's array of ItemType items
int mySize; // Heap's size
void percolateUp(int);
void ReHeap(int);
};Heap.cpp
#include <iostream>
#include <algorithm>
#include "Heap.h"
using namespace std;
// Default constructor -- initializes mySize to represent an empty Heap.
template <class ItemType>
Heap<ItemType>::Heap()
{
mySize = 0;
}
// This function returns true (empty Heap) or false depending on the Heap's
// size.
template <class ItemType>
bool Heap<ItemType>::isEmpty() const
{
return (mySize == 0);
}
// This function returns true (full Heap) or false depending on the Heap's
// size.
template <class ItemType>
bool Heap<ItemType>::isFull() const
{
return (mySize == MAX_SIZE);
}
// This function returns the Heap array index of the left child of the node
// whose index is passed into arugment "root"
template <class ItemType>
int Heap<ItemType>::Left(int root) const
{
if (root >= 0 && (2 * root + 1) <= mySize) // If "root" is in the Heap
// and it can possibly have
// a left child...
return (2 * root + 1); // Returns that left child's
// position
else
return -1; // Otherwise, returns a value
// to indicate no left child
// is possible
}
// This function returns the Heap array index of the left child of the node
// whose index is passed into arguement "root"
template <class ItemType>
int Heap<ItemType>::Right(int root) const
{
if (root >= 0 && (2 * root + 2) <= mySize) // If "root" is in the Heap
// and it can possibly
// have a right child...
return (2 * root + 2); // Returns that right
// child's position
else
return -1; // Otherwise, returns a
// value to indicate no
// right child is possible
}
// This function returns the Heap array index of the parent of the node whose
// index is passed into argument "child"
template <class ItemType>
int Heap<ItemType>::Parent(int child) const
{
if (child > 0 && child <= mySize) // If "child" is in the Heap
// and is not the root node...
return (child - 1) / 2; // Returns the parent node's
// position
else
return -1; // Otherwise returns a value to
// indicate no parent node exists
}
// This function accepts the new "item" value as its argument. It works by
// inserting the new item at the end of the heap, and calling percolateUp() to
// swap positions with the parent, but only if the parent has a smaller value
// than the new item. If the Heap is full, the item will not be inserted and an
// error will be displayed.
template <class ItemType>
void Heap<ItemType>::insert(const ItemType &item)
{
if (isFull() == TRUE)
cout << "ERROR: Heap is full!\n\n"; // Heap is full-- throw an error
else
{
myArray[mySize] = item; // Places "item" at the end of the
// Heap's array
percolateUp(mySize); // Moves the item "up" the Heap
// until the correct position
// is found
mySize++;
}
}
// This function is used in conjunction with insert(). It is a recursive
// function that moves an item up the Heap as long as that item is greater than
// its parent.
template <class ItemType>
void Heap<ItemType>::percolateUp(int index)
{
int parent = Parent(index); // Get the parent's position in the Heap
if (parent >= 0 && myArray[index] > myArray[parent]) // The parent exists and
// is lesser in value
// than the current
// item...
{
swap(myArray[index], myArray[parent]); // Swap the values of the parent
// and the current item
percolateUp(parent); // Recursively apply this
// function to the freshly
// swapped item
}
}
// This function removes the item with the highest priority and returns its
// value. The item is swapped with the last item in the Heap's array, and
// mySize is decremented. The item should not be physically deleted as it will
// remain as part of the array. However, It will not be part of the Heap since
// mySize will be updated, and the heap goes only as far as (mySize - 1). The
// new root may not have the largest priority, therefore the ReHeap() function
// should be used to move the new root into its proper position, thus
// conserving the heap property.
template <class ItemType>
ItemType Heap<ItemType>::removeMax()
{
if (!isEmpty()) // The Heap is not empty, proceed...
{
int maxItem = myArray[0]; // The max item in a heap is the
// root
swap(myArray[0], myArray[mySize - 1]); // Swap the value of the root with
// the value of the last
// element in the Heap's array
mySize--;
ReHeap(0); // Apply ReHeap() to the new root!
return maxItem; // Returns the maximum value
// (the old root)
}
}
// The ReHeap() function checks if either of root's children are greater than it
// is, in which case the greater child is swapped with "root." The process is
// then continued on the children of "root" using recursion. The function stops
// when "root" is greater than both of its children.
template <class ItemType>
void Heap<ItemType>::ReHeap(int root)
{
int largest = root; // The largest should start out as argument
// "root"
int left = Left(root); // Position of left child of "root"
int right = Right(root); // Position of right child of "root"
if (left < mySize && myArray[left] > myArray[root])
largest == left; // The left child of "root" is in the array
// and is greater than "root"
if (right < mySize && myArray[right] > myArray[largest])
largest = right; // The right child of "root" is in the array
// and is greater than "root"
// and/or the left child of "root"
if (largest != root) // The largest value is not "root"...
{
swap(myArray[root], myArray[largest]); // Swap "root" with the value
// that is larger
ReHeap(largest); // Recursively call ReHeap() on
// the new larger value
}
}
// This function displays the entire Heap by ouputting its array in index-order
template <class ItemType>
void Heap<ItemType>::display() const
{
if (!isEmpty())
{
for(int i = 0; i < mySize; i++)
{
cout << myArray[i] << " ";
}
cout << endl;
}
}main.cpp
/* --- main.cpp ----------------------------------------------------------------
This program randomly generates 30 integers between 10 and 200 and inserts
them into a Heap. The Heap is then used to sort the integers in descending
order by storing them in an array as they are pulled off the Heap. The Heap
ADT is implemented using a class.
------------------------------------------------------------------------------*/
#include <iostream>
#include <algorithm>
#include <time.h>
#include "Heap.h"
using namespace std;
int main()
{
srand(time(NULL)); // Seeds the random number generator
Heap<int> heap; // The Heap object
int newNumber;
int array[MAX_SIZE]; // The array to store the Heap-sorted integers
// Generates the Heap
char *s = "Generating Heap - Please Wait...";
*s = '\n';
cout << *s << endl << endl;
for (int i = 0; i < MAX_SIZE; i++)
{
newNumber = rand() % 190 + 10; // Generates a new random integer
// between 10 and 200
heap.insert(newNumber); // Inserts this new random integer
// into the heap
}
// Displays the Heap in array form and un-sorted
cout << "THE RAW HEAP:\n====================\n";
heap.display();
// Generates & displays the sorted array
cout << "\n\nSORTED ARRAY:\n====================\n";
for (int i = 0; i <= MAX_SIZE; i++)
{
array[i] = heap.removeMax(); // Fills array element i with the
// freshly removed maximum value
// from the Heap
cout << array[i] << " "; // Displays array element i
}
cout << endl;
return 0;
}---------------------------------------------------------------------------------------
When I try to compile all of this in cygwin ( g++ -o main main.cpp Heap.cpp Heap.h ), I get the follow errors:
main.cpp: In function 'int main()':
main.cpp:24: warning: deprecated conversion from string constant to 'char*'
Heap.cpp: In member function 'void Heap<ItemType>::insert<const ItemType&>':
Heap.cpp:85: error: 'TRUE' was not declared in this scope
I don't know how to fix these. I have tried a couple of things but to no avail. Your input would be much appreciated. Thank you!
