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!

Edited by Toxic_Rice: n/a

4
Contributors
20
Replies
21
Views
6 Years
Discussion Span
Last Post by Toxic_Rice
Featured Replies
• 1

You can ignore the warning. For line 85, TRUE should be in lower case ----> [CODE]if (isFull() == true)//Lower case!![/CODE]

• 1

You cannot as of right now, seperate the template definition from its implementation. They both need to go in the same file.

• 1

Probably if you use MinGW compiler you won't get the warning. By the way, it's not an error it's a warning that in this case you can simply ignore it. Say in MinGW if you compile a C++ code using gcc you may get this warning. So as long as …

• 1

Discard the [I]char*[/I] and use [I]std::string[/I]

• 1

Line 42, [CODE]for (int i = 0; i <= MAX_SIZE; i++)[/CODE] get rid of "=" sign, [CODE]for (int i = 0; i < MAX_SIZE; i++)[/CODE] It should work. I have no access to C++ compiler currently, so report back if it didn't work.

You can ignore the warning.

For line 85, TRUE should be in lower case ---->

``if (isFull() == true)//Lower case!!``

Thank you, group256, for the fast response! That TRUE error went away when you suggested the lower case. However, the 'warning' on line 24 in main.cpp still exists, and on top of that, I have given birth to new errors:

tmp/ccegi5Id.o:main.cpp:<.text+0xae>: undefined reference to 'Heap<int>::Heap()'
tmp/ccegi5Id.o:main.cpp:<.text+0xae>: undefined reference to 'Heap<int>::insert(int const&)
tmp/ccegi5Id.o:main.cpp:<.text+0xae>: undefined reference to 'Heap<int>::display() const'
tmp/ccegi5Id.o:main.cpp:<.text+0xae>: undefined reference to 'Heap<int>::removeMax()'
collec2: ld returned 1 exit status

I do not understand why I am getting this. I also do not understand why you said the 'warning' could be ignored.

Edited by Toxic_Rice: n/a

You cannot as of right now, seperate the template definition from its implementation. They both need to go in the same file.

Ah. Yes! Thank you firstPerson. That makes sense because when you use templates, the function prototypes and definitions should be in the same header file. However, I'm still having this error:

main.cpp:24: warning: deprecated conversion from string constant to 'char*'

And I have no clue how to get rid of it. I tried looking on Google on the error, but I can't see to implement it in my code.

I tried changing it to char s[] = "string";
I tried char *s[] = "string";

Probably if you use MinGW compiler you won't get the warning. By the way, it's not an error it's a warning that in this case you can simply ignore it.

Say in MinGW if you compile a C++ code using gcc you may get this warning. So as long as your program is working, nothing to worry about. That's all I know, but why it's generated, honestly, I don't know either.

Discard the char* and use std::string

Hmmm. That is very strange, group256. I have never encountered a 'warning' up until this program. The reason for using std::string instead of char* is still unknown to me, but thanks to firstPerson, the program compiled successfully with no errors or warnings. Thank you firstPerson and group256, again.

When I run the program, I was very excited. However, I get a Segmentation fault <core dumped> at the very end of my display:

THE RAW HEAP:
===============================
190 173 183 162 81 180 163 158 100 47 43 143 155 143 132 62 20 95 55 29 12 28 16 20 35 68 72 23 112 71

SORTED ARRAY:
===============================
190 183 163 132 13238700 112 72 71 68 35 28 29 55 95 23 62 20 143 155 143 43 47 100 158 20 180 81 162 16 173 0
Segmentation fault <core dumped>

'THE RAWP HEAP:' section of the program appears to be correct. It generates 30 random numbers. 'SORTED ARRAY:' section of the program appears to be correct at first, but as you go down the array, you see some funky business.

I have seen this Segmentation fault many times. I looked around in my program and tried to see if anything was off. I looked mainly at lines 42-48 of main.cpp to make sure the sorting was correct. I can't find any errors. The comments seem to make sense to me. Again, I appreciate the help, and thank you for sticking with me.

Line 42,

``for (int i = 0; i <= MAX_SIZE; i++)``

get rid of "=" sign,

``for (int i = 0; i < MAX_SIZE; i++)``

It should work. I have no access to C++ compiler currently, so report back if it didn't work.

Very nice, group256. The program did work with no errors, warnings,or segmentation faults. Thank you for that fix! Unfortunately, the 'SORTED ARRAY:' section of the program seems to be outputting incorrect results. Here is the display:

THE RAW HEAP:
=========================
197 158 191 143 151 135 179 36 116 73 138 68 124 87 165 23 31 97 97 53 68 78 123 16 42 51 101 16 54 65

SORTED ARRAY:
=========================
197 191 179 165 165 101 65 54 123 78 68 53 97 97 51 42 31 87 124 68 138 73 116 36 23 135 151 143 16 158

I have a feeling that the mistake might be in the removeMax() implementation. I'm not quite sure what to make of this, but I will mess around with the removeMax() to see if that is the problem. If anyone has any suggestions or fixes for the incorrect output of the 'SORTED ARRAY:' section, please share your input. Thank you. (... and thank you, group256).

Edited by Toxic_Rice: n/a

In `ReHeap()` , comparison is used instead of assignment ..

``````if (left < mySize && myArray[left] > myArray[root])
largest == left; // <--- Wrong``````

You should catch this by enabling basic warnings, i.e. compiling with e.g. `-Wall -Wextra` .

Also in `ReHeap()` , check that `left` and `right` are not negative when indexing into the `myArray` .

I see. Thank you so much, mitrmkar! To be honest, I have never heard of that -Wall and -Wextra commands. In Cygwin, I don't have the slightest clue on how to execute those commands, but I will search Google to find out. Thank you for those and the fix! I believe, when I was compiling the code, I got a little zealous with those equal signs. My nightmare is almost over.
The 'SORTED ARRAY:' section does put the numbers in descending order. And to backtrack, I checked if the left and right were negative when being put into the array. However, there is one guy who is not cooperating with everyone else. Here is the output of one run:

THE RAW HEAP:
===========================
196 192 192 180 182 179 188 115 139 127 150 108 123 180 113 23 87 24 111 17 111 122 131 96 51 23 58 142 26 34

SORTED ARRAY:
===========================
196 192 192 188 182 180 180 179 150 142 139 131 12714412 127 123 122 115 113 111 111 108 96 87 58 51 34 26 24 23 23

That number, 12714412, is really throwing me off. I do not know what could be the problem. It may reside the ReHeap() section. I will see. If anyone has a fix for this, please share your input! Thank you again, mitrmkar, and thank you to everybody who has helped me this far.

Pass the warning options on the commandline i.e. `g++ -Wall -Wextra` and first get a clean compile.

As to the surprise number, I believe you might be stepping outside array boundaries, which are 0..N-1, inclusive.

Ok. I see how to use that command now. Thanks, mitrmkar. When I ran the -Wall command for main.cpp, I ran into this warning:

Heap.h:203: warning: control reaches end of non-void function

I typed that warning in Google, and I'm just guessing that the compiler is complaining about no return statement at that line. It can't tell that the program can't reach this point.

When I tried to put 'return maxItem;' out of the 'if' statement, the compiler is complaining about how maxItem is not defined. Is that what I'm supposed to do?

Also, the array boundaries do make sense, mitrmkar. So I'm guessing I should change i < MAX_SIZE in the for loop of main.cpp to i < MAX_SIZE - 1?

I do not know what is causing that weird number. If anyone has any fixes, please share your input. Thanks again, mitrmkar.

>> When I tried to put 'return maxItem;' out of the 'if' statement, the compiler is complaining about how maxItem is not defined. Is that what I'm supposed to do?

Strictly speaking: change your code so that you don't get that warning anymore.

About the boundaries, if you have an array of N elements, then you are allowed to access indices 0..N-1, inclusive, i.e.

``````const int ARR_SIZE = 3;
// An array, all elements initialized to zero
int array[ARR_SIZE] = {0};

for(int ii = 0; ii < ARR_SIZE; ++ii)
{
// Do something with array[ii] here ..
}``````

Thank you, mitrmkar. But I'm a little confused. I thought I did that with the 'SORTED ARRAY:' section.

``````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
}``````

I am allowing access to all of the indices. From 0 to MAX_SIZE (which is 30 in this case).

But I'm a little confused. I thought I did that with the 'SORTED ARRAY:' section ...

Yes, you did that correctly, however, I was suggesting that you might be stepping out of boundaries wrt. the heap's `myArray[]`

I think I may almost have it. Thanks for the tips. Your last post kind of tipped me off to do this with my code:

In main.cpp

``````int main()
{
srand(time(NULL));      // Seeds the random number generator

Heap<int> heap;         // The Heap object
int newNumber;
int array[MAX_SIZE-1];        // The array to store the Heap-sorted integers **** This is what I changed. int array[MAX_SIZE] to int array[MAX_SIZE-1]``````

I almost have the output as well:

THE RAW HEAP:
=========================
197 173 184 149 171 181 167 126 149 167 170 160 42 143 147 40 33 87 41 89 137 110 69 68 42 20 22 47 136 92

SORTED ARRAY:
=========================
197 184 181 173 171 170 167 160 149 149 147 143 137 136 126 110 92 89 87 69 68 47 42 42 41 40 33 22 20
Segmentation fault <core dumped>

Do you, mitrmkar, or anybody have any fixes or tips to this Segmentation fault? I'm almost there. Thank you for helping me this far.

How about forgetting the extra array in `main()` (do you really need it at this point?), and instead go along the lines of ..

``````int main()
{
srand(time(NULL));      // Seeds the random number generator
Heap<int> heap;         // The Heap object

while(!heap.isFull())
{
heap.insert(rand() % 190 + 10);
}

heap.display();

while(!heap.isEmpty())
{
cout << heap.removeMax() << " ";
}
cout << endl;

return 0;
}``````

>> tips to this Segmentation fault

You might use assert() as an aid in spotting out-of-bounds reads/writes. In other words, throughout your code, assert every access to the heap's array, like so

``````assert(index >= 0);
assert(index < mySize);
assert(parent < mySize);
assert(parent >= 0);
if (myArray[index] > myArray[parent])``````

Edited by mitrmkar: assert

Thank you, mitrmkar! I got it working properly now. The display is a success. The boss says, I'm violating two coding standards? I don't get it...

But this is pretty much the end. Thank you everybody for helping me out this far. I'll mark this thread solved once I get the final input from somebody. Thank you all very much.

Thank you, mitrmkar! I got it working properly now. The display is a success. The boss says, I'm violating two coding standards? I don't get it...

But this is pretty much the end. Thank you everybody for helping me out this far. I'll mark this thread solved once I get the final input from somebody. Thank you all very much.