CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Mar 2015
    Posts
    64

    [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:
    Name:  ***_heap.jpg
Views: 590
Size:  25.6 KB

    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?

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    May 2001
    Location
    Germany
    Posts
    1,158

    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--)

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  5. #5
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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)

  6. #6
    Join Date
    Mar 2015
    Posts
    64

    Re: Dequeuing Integer Values From Heap Results In Garbage Values

    I can't believe I missed that! That was it. Thanks Richard.

  7. #7
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Dequeuing Integer Values From Heap Results In Garbage Values

    Quote Originally Posted by UncleBazerko View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured