-
April 8th, 2015, 07:21 PM
#1
[RESOLVED] Dequeuing Integer Values From Heap Results In Garbage Values
Hi. I've been working on a homework assignment that randomly generates integers and populates them into an array (array1). The program is then supposed to:
1.) copy those values to a second empty array (array2)
2.) sort the values already in array1 (using an inline function)
3.) enqueue the unsorted integers from array2 into a heap vector
4.) a third empty array (array3) is supposed to be populated with those unsorted integers (by dequeuing them from the heap), sorted in reverse order.
But no matter what I do, I always get garbage values like these:
I've tried using both a standard random number generator:
array1[i] = rand()%100+1;
And the d_random.h file my instructor gave us, but nothing works. My friends and peers can't figure out why. The tutors can't figure out why. Not even my instructor can figure out why!
Here's the code from all 3 files:
HeapTester.cpp
Code:
#include <iostream> // Provides cin, cout
#include <cstdlib> // Provides EXIT_SUCCESS, rand, srand
#include "d_random.h" //Provides random number generator
#include "Heap.h"
using namespace std; // Use C++ Standard namespace
//Elements in each array.
const int arrayLength = 15;//100;
void printArray(const int data[], int n);
void selectionSort(int data[], int n);
//Main method to test implementation of heap
int main()
{
//Create two empty arrays fill with the same random ints from 1 to 100
int array1[arrayLength];
int array2[arrayLength];
randomNumber r;
//srand(time(NULL));//initialize random seed
for (int i = 0; i<arrayLength; i++)
{
//array1[i] = rand() % 100 + 1;
//cout << array1[i] << ", ";
array1[i] = r.random(100)+1;
array2[i] = array1[i];
}
//print the unsorted array
cout << "Unsorted elements in array2 copied from array1: " << endl;
printArray(array2, arrayLength);
//sort the first array with selection sort
cout << "\n\nRunning Selection Sort on array1! Please wait." << endl;
selectionSort(array1, arrayLength);
cout << "\n Selection Sort done." << endl;
//Implement HeapSort
cout << "\n HeapSort Started." << endl;
//Create heap h1.
heap <int> h1;//instance of vector v
//Using a for loop enqueue on h1 all numbers stored in array2.
for (int i = 0; i< arrayLength; i++)
{
h1.enqueue(array2[i]);//move all elements from array2 to heap (array2[i] = entry)
}
//Create array array3 of size arrayLength
int array3[arrayLength];
//Dequeue all element in the heap h1 into array3 (try storing in reverse order for extra challenge)
//for(int i = 0; i < h1.size(); i++)
for (int i = h1.size() - 1; i < 0; i--)
{
array3[i] = h1.dequeue();
}
//Print array array3 to demonstrate that elements are sorted
printArray(array3, arrayLength);
return EXIT_SUCCESS;
}//end of main
void selectionSort(int data[], int n)
{ // Precondition: data contains n elements
// Postcondition: data is sorted in ascending order
int smallestIndex;
int smallest, saved;
for (int i = 0; i < n - 1; i++)
{ // Find smallest element
smallest = data[i];
smallestIndex = i;
for (int j = i + 1; j < n; j++)
if (data[j] < smallest)
{
smallest = data[j]; smallestIndex = j;
}
// Swap with smallest element
saved = data[i]; data[i] = data[smallestIndex];
data[smallestIndex] = saved;
}
}
//method to print out an array with 10 items per line
void printArray(const int data[], int n)
{
//Precondition: data contains n elements
//Postcondition: output data array to screen with 10 elements per line
cout << endl << "The array elements are ";
for (int i = 0; i < n; i++)
{
if (i % 10 == 0)
cout << endl;
cout << data[i] << " ";
}
cout << endl << endl;
}
Heap.h
Code:
#include <vector>
using namespace std;
template <typename T>
class heap
{
public:
// Constructor: creates an empty heap.
heap(){}
//add an item to the heap and re-adjust tree accordingly
void enqueue(const T& entry);
//remove an item from the heap and re-adjust tree accordingly
T dequeue();
// return the current size of the bag (size of v)
int size() const{ return v.size(); }
void printHeap();
private:
//restore heap by swapping the element up the heap
void reheapifyUp(size_t curSpot);
//restore heap by swapping the element down the heap
void reheapifyDown(size_t curSpot);
// Heap elements stored in a vector v
vector<T> v;
};
template <typename T>
void heap<T>::reheapifyUp(size_t curSpot)
{
//Find the index of your parent node
size_t parentIndex = (curSpot - 1) / 2;
// Swap element at curSpot up the tree to form a heap.
// Stop at root or when element less than parent
while (curSpot>0 && v[curSpot]>v[parentIndex])
{
T temp = v[curSpot];
v[curSpot] = v[parentIndex];
v[parentIndex] = temp;
curSpot = parentIndex;
parentIndex = (curSpot - 1) / 2;
}
}
template <typename T>
void heap<T>::enqueue(const T& entry)
{
//Push key onto back of v vector
v.push_back(entry);
//call reheapifyUp with the index of the newly inserted key
reheapifyUp(size() - 1);
}
template <typename T>
void heap<T>::reheapifyDown(size_t curSpot)
{ //Declare child indices and largest index
size_t lchild = curSpot * 2 + 1;
size_t rchild = curSpot * 2 + 2;
//While not at a leaf node
while (lchild < size())
{ //Find largest of two children (check if rchild exists)
size_t largest;
if (rchild<size() && v[lchild]<v[rchild])
largest = rchild;
else
largest = lchild;
//break from the loop is both children less than parent
if (v[curSpot] >= v[largest])
break; // key is >= children, can stop
//swap curSpot and parent elements
T temp = v[curSpot];
v[curSpot] = v[largest];
v[largest] = temp;
//Reset curSpot and its children indices
curSpot = largest;
lchild = curSpot * 2 + 1;
rchild = curSpot * 2 + 2;
}
}
template <typename T>
T heap<T>::dequeue()
{
//Store root element on top of the heap in a temp variable
T temp = v[0];
//copy last element into first location
v[0] = v[size() - 1];
//remove last element (back of vector)
v.pop_back();
//reheapify the new root element down the tree with reheapifyDown
reheapifyDown(0);
//return stored temp element
return temp;
}
//add to header.
template <typename T>
void heap<T>::printHeap()
{
for (int i = 0; i<size(); i++)
{
cout << v[i] << " ";
}
}
d_random.h
Code:
#include <iostream>
#include <time.h>
using namespace std;
// generate random numbers
class randomNumber
{
public:
// initialize the random number generator
randomNumber(long s = 0);
// return a 32-bit random integer m, 1 <= m <= 2^31-2
long random();
// return a 32-bit random integer m, 0 <= m <= n-1,
// where n <= 2^31-1
long random(long n);
// return a real number x, 0 <= x < 1
double frandom();
private:
static const long A;
static const long M;
static const long Q;
static const long R;
long seed;
};
const long randomNumber::A = 48271;
const long randomNumber::M = 2147483647;
const long randomNumber::Q = M / A;
const long randomNumber::R = M % A;
randomNumber::randomNumber(long s)
{
if (s < 0)
s = 0;
if (s == 0)
{
// get time of day in seconds since 12:00 AM,
// January 1, 1970
long t_time = time(NULL);
// mix-up bits by squaring
t_time *= t_time;
// result can overflow. handle cases
// > 0, < 0, = 0
if (t_time > 0)
s = t_time ^ 0x5EECE66DL;
else if (t_time < 0)
s = (t_time & 0x7fffffff) ^ 0x5EECE66DL;
else
s = 0x5EECE66DL;
}
seed = s;
}
long randomNumber::random()
{
long tmpSeed = A * (seed % Q) - R * (seed / Q);
if (tmpSeed >= 0)
seed = tmpSeed;
else
seed = tmpSeed + M;
return seed;
}
long randomNumber::random(long n)
{
double fraction = double(random()) / double(M);
return int(fraction * n);
}
double randomNumber::frandom()
{
return double(random()) / double(M);
}
I need a hero
Can anybody figure out why I'm getting those garbage values?
-
April 9th, 2015, 01:00 AM
#2
Re: Dequeuing Integer Values From Heap Results In Garbage Values
Your printing of the initial array elements indicate that there is nothing wrong with the random number generation. I suggest that you also print the array after the selection sort. If there is nothin wrong with that output, then the problem almost certainly lies with your implementation of heap sort.
-
April 9th, 2015, 01:33 AM
#3
Re: Dequeuing Integer Values From Heap Results In Garbage Values
This
Code:
for (int i = h1.size() - 1; i < 0; i--)
is wrong. Your loop is never executed because "i < 0" is false. It should read
Code:
for (int i = h1.size() - 1; i >= 0; i--)
-
April 9th, 2015, 02:51 AM
#4
Re: Dequeuing Integer Values From Heap Results In Garbage Values
In situations like this the first thing to do is to use the debugger to trace through the program to see where the execution deviates from that expected from the program design. Trace execution flow and monitor variable values as the program executes then you'll see where the problem lies.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
April 9th, 2015, 04:42 AM
#5
Re: Dequeuing Integer Values From Heap Results In Garbage Values
Why are you trying to re-invent the wheel with your own random number class? Why not use the standard c++11 one? See
http://www.cplusplus.com/reference/random/
http://forums.codeguru.com/showthrea...ghlight=random
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
April 9th, 2015, 11:22 AM
#6
Re: Dequeuing Integer Values From Heap Results In Garbage Values
I can't believe I missed that! That was it. Thanks Richard.
-
April 11th, 2015, 04:47 PM
#7
Re: Dequeuing Integer Values From Heap Results In Garbage Values
Originally Posted by UncleBazerko
I can't believe I missed that! That was it. Thanks Richard.
Do yourself a favor and Learn to use a debugger. The debugger would have told you that faster than it took you to copy paste your code here.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|