Skip to main content
GameDev.net gamedev.net
🔒 Locked 🎮 Unity

Priority heap problem.

Started by McZ Dec 16, 2005 at 8:53 AM 5 replies 500+ views
Original Post
McZ
McZ
I'm trying to implement a priority heap at school but it doesn't work when adding more than 289 elements, well actually the adding works but it doesn't work when to dequeue them. This is the situation, I should add X elements to the array and take the time for the process of it, and then I should check how long it will take to dequeue them. like this: 

timer->start();

for( int i=0; i<SIZE; i++ )
{
 heap->enqueue( rand() );
}

float enqueue_time = timer->end();

timer->start();

while( !heap->isEmpty() )
{
 heap->dequeue();
};

float dequeue_time = timer->end();
I should test the SIZE with sizes 100000, 500000, 1000000, 5000000, all of them works when enqueue only, it crasch when trye to dequeue the items. altough if SIZE is 289 then it works to dequeue. Heap source 

#ifndef CHeap_H
#define CHeap_H

#include "CPriorityQueue.h"

template <class T>
class CHeap : public CPriorityQueue<T> {

	int	m_iMaxSize;		//!< Size of heap. Default 10
	int	m_iLastItem;	//!< Last item index in array
	T	*m_pHeap;		//!< Heap array.

	void reheapUp(int index)
	{
		if ( index == 0 )
			return;

		int parent = ((index+1) / 2)-1;

		if( m_pHeap[parent] > m_pHeap[index] )
			return;

		T saveItem = m_pHeap[index];

		m_pHeap[index] = m_pHeap[parent];
		m_pHeap[parent] = saveItem;

		reheapUp(parent);
	}

	void reheapDown(int index)
	{
		int swap = (2 * (index+1))-1;

		if( (m_pHeap[index] > m_pHeap[swap]) && (m_pHeap[index] > m_pHeap[swap+1]) )
			return;

		if( m_pHeap[swap] < m_pHeap[swap+1] )
			swap++;

		if( swap > m_iLastItem )
			return;

		T saveMe = m_pHeap[index];
		m_pHeap[index] = m_pHeap[swap];
		m_pHeap[swap] = saveMe;

		reheapDown(swap);
	}

public:

	CHeap(int size=10)
	{
		m_iMaxSize = size;
		m_iLastItem = -1;
		m_pHeap = new T[m_iMaxSize];
	}

	void enqueue( T o )
	{
		m_iLastItem++;
		m_pHeap[m_iLastItem] = o ;

		if( m_iLastItem > 0 )
		{
			reheapUp(m_iLastItem);
		}
	}

	T dequeue()
	{ 
		if( isEmpty() )
			throw QUEUE_EMPTY;

		T removeMe = m_pHeap[0];
		m_pHeap[0] = m_pHeap[m_iLastItem];

		reheapDown(0);

		m_iLastItem--;
		return removeMe;
	}

	T peek()
	{ return m_pHeap[0]; }

	bool isFull()
	{ return (m_iLastItem >= m_iMaxSize); }

	bool isEmpty()
	{ return (m_iLastItem < 0); }

	int getSize()
	{
		return m_iLastItem;
	}

	void destroyQueue()
	{
		if( m_pHeap != NULL )
			delete m_pHeap;
	}

	/**
		Print queue to standard output.
	*/
	void printQueue()
	{
		cout << "----------------" << endl;
		for( int i=0; i<m_iLastItem; i++ )
		{
			cout << "(" << i <<  ") " << m_pHeap << endl;
		}
		cout << "----------------" << endl;
	}
};

#endif // CHeap_H
[/soucre]

Heap template is using integer in test program CHeap<int> heap;
Enigma
Enigma
What does your debugger say? Hint: if you can't figure out what's going on from the debugger try manually walking through dequeue on a heap with two elements (say 2 and 1), i.e.:
T dequeue() // heap == {2, 1}{	if( isEmpty() ) // step into isEmpty// stepping into isEmptybool isEmpty(){ return (m_iLastItem < 0); } // m_iLastItem == 1, so returns false// returning to dequeue	if( /*isEmpty()*/ false ) // isEmpty() returned false		throw QUEUE_EMPTY; // does not execute	T removeMe = m_pHeap[0]; // removeMe == 2	m_pHeap[0] = m_pHeap[m_iLastItem]; // heap == {1, 1}	reheapDown(0); // exercise for the reader - step into reheapDown	// following assumes that reheapDown does not affect m_iLastItem	m_iLastItem--; // m_iLastItem == 0	return removeMe; // return 2}


Enigma
iMalc
iMalc
Try adding some assert()'s to check you array indexes.
When you deque the items, are they correct?
Can you give us any indication of where it's crashing?
Also, it would be nicer if you simplified:
		int swap = (2 * (index+1))-1;
to just
		int swap = 2 * index + 1;
and
		int parent = ((index+1) / 2)-1;
to just
		int parent = (index - 1) / 2;
McZ
McZ
Quote:
Original post by iMalc
Try adding some assert()'s to check you array indexes.
When you deque the items, are they correct?
Can you give us any indication of where it's crashing?
Also, it would be nicer if you simplified:
		int swap = (2 * (index+1))-1;
to just
		int swap = 2 * index + 1;
and
		int parent = ((index+1) / 2)-1;
to just
		int parent = (index - 1) / 2;




As long as the application works the dequeue works as it is supposed to do.
Enigma
Enigma
It appears that you have not yet learnt that "appears to work" does not mean your code is correct when dealing with C++. For example, indexing out of bounds of an array is undefined behaviour, so if you do something like:
#include <iostream>int main(){	int array[4] = {0, 1, 2, 3};	if (array[3] < array[4])	{		std::cout << "array[3] < array[4]\n";	}	else	{		std::cout << "array[3] >= array[4]\n";	}}

Then your program could legitimately print "array[3] < array[4]", or it could legitimately print "array[3] >= array[4]", or it could legitimately print "I don't like you anymore", or it could legitimately crash, or it could legitimately start world war 3, or... The behaviour is undefined. It could do anything. It can even change from one run to another (although for fixed-path code it tends not to). asserts, debuggers and the ability to manually check code can help to detect undefined behaviour that you would not have otherwise spotted (because the actual behaviour happened not to have any effect on your program).

In other words, I know exactly what your error is (or at least one of them), and I suspect iMalc does too (or at least has a sneaking suspicion). We're not telling you the answer because it's school work (or at least that's what I understand from "I'm trying to implement a priority heap for school) and you need to learn for youself (the old "give a man a fish" versus "teach a man to fish" adage) but we've given you enough hints to nudge you in the right direction.

Enigma
iMalc
iMalc
Quote:
Original post by McZ
Quote:
Original post by iMalc
Try adding some assert()'s to check your array indexes.
When you deque the items, are they correct?
Can you give us any indication of where it's crashing?
Also, it would be nicer if you simplified:
As long as the application works the dequeue works as it is supposed to do.
Excuse me!?! Your program is crashing because you have a bug.
If you want anyone at all to help you, you'll have to do your best to answer any questions people may have, and try people's advice.

In the following code you are not checking the return value of dequeue
Quote:
while( !heap->isEmpty() ){ heap->dequeue();};
Therefore, all you can say about that loop, is whether or not it terminates.
What you may need is a heapVerify function which when called, checks that the heap properties are all correct, and this can be called after each time you perform operations on the heap which modify it.

Here's some more useful tips:
1. In destroyQueue you do not need the line
		if( m_pHeap != NULL )
because delete already checks for nulls before doing anything.

2. You are supposed to use delete[] when using new[], ommitting the [] is an error.

3. Your peek function should probably throw an exception when the heap is empty, just like your dequeue function.

4. Your code maintains m_iLastItem as an index to the last item in the heap, instead of one past it, as is done in the STL (for good reason I might add). Thus your for loop in printQueue is wrong. It would need to be:
		for( int i=0; i<=m_iLastItem; i++ )

5. Following on from (4), this means that your isFull fucntion has an off by one error because by the time m_iLastItem = m_iMaxSize you have already overflowed the buffer by one element. Thus I'd strongly suggest changing your code so that m_iLastItem stores the index to the item after the last valid item, which has numerous other advantages. Meaning of course, you wouldn't make the change listed in (4), but would modify your constructor, enqueue, dequeue and isEmpty functions.

6. getSize has the same off by one error as in (5).

I think that's far more help already than I should have given, as I've just remembered that you said this is for school, so I suggest you read the faq and finish the thing yourself.

[Edited by - iMalc on December 16, 2005 9:27:09 PM]
McZ
McZ
Thank you for all help, and for not giving me to much help.

This is my new updated heap code this works(at least it doesn't crash) with enqueue/dequeue 5000000 objects of type int.
#ifndef CHeap_H#define CHeap_H#include <assert.h>#include "CPriorityQueue.h"template <class T>class CHeap : public CPriorityQueue<T> {	int	m_iMaxSize;		//!< Size of heap. Default 10	int	m_iLastItem;	//!< Last item index in array	T	*m_pHeap;		//!< Heap array.	void reheapUp(int index)	{		if ( index <= 0 )			return;		int parent = (index-1) / 2;		if( parent < 0 )			return;		assert( parent >= 0 );		assert( parent < m_iLastItem );		if( m_pHeap[parent] > m_pHeap[index] )			return;		T saveItem = m_pHeap[index];		m_pHeap[index] = m_pHeap[parent];		m_pHeap[parent] = saveItem;		reheapUp(parent);	}	void reheapDown(int index)	{		int swap = 2 * index + 1;		assert( swap >= 0 );		assert( index >= 0 );		if( swap > m_iLastItem || index > m_iLastItem )			return;		assert( index < m_iLastItem );		assert( swap <= m_iLastItem );		if( (m_pHeap[index] > m_pHeap[swap]) && (m_pHeap[index] > m_pHeap[swap+1]) )			return;		if( m_pHeap[swap] < m_pHeap[swap+1] )			swap++;		if( swap > m_iLastItem )			return;		T saveMe = m_pHeap[index];		m_pHeap[index] = m_pHeap[swap];		m_pHeap[swap] = saveMe;		reheapDown(swap);	}public:	CHeap(int size=10)	{		m_iMaxSize = size;		m_iLastItem = -1;		m_pHeap = new T[m_iMaxSize];	}	void enqueue( T o )	{		m_iLastItem++;		m_pHeap[m_iLastItem] = o ;		if( m_iLastItem > 0 )		{			reheapUp(m_iLastItem);		}	}	T dequeue()	{ 		if( isEmpty() )			throw QUEUE_EMPTY;		T removeMe = m_pHeap[0];		m_pHeap[0] = m_pHeap[m_iLastItem];		reheapDown(0);		m_iLastItem--;		return removeMe;	}	T peek()	{ return m_pHeap[0]; }	bool isFull()	{ return (m_iLastItem >= m_iMaxSize-1); }	bool isEmpty()	{ return (m_iLastItem < 0); }	int getSize()	{		return m_iLastItem;	}	void destroyQueue()	{		if( m_pHeap != NULL )			delete[] m_pHeap;	}	/**		Print queue to standard output.	*/	void printQueue()	{		cout << "----------------" << endl;		for( int i=0; i<=m_iLastItem; i++ )		{			cout << "(" << i <<  ") " << m_pHeap << endl;		}		cout << "----------------" << endl;	}};#endif // CHeap_H

it would be nice if you have time to look and see if there are anything I have missed, don't say what it is just give me a hint.

iMalc>
Quote:

Excuse me!?! Your program is crashing because you have a bug.
If you want anyone at all to help you, you'll have to do your best to answer any questions people may have, and try people's advice.


I know there is a bug because it crash when there are to many objects but the enqueue dequeue did give me correct result when testing with few objects <200. altough the tests wasn't all the combinations so it might have failed if I continued.

Quote:

Here's some more useful tips:
1. In destroyQueue you do not need the line

if( m_pHeap != NULL )

because delete already checks for nulls before doing anything.


Yes I know I don't need to check that. But I do it because one time I had to add that line else the application crashed on the delete line.

Quote:

2. You are supposed to use delete[] when using new[], ommitting the [] is an error.


same as above. I once used delete[] on an array created with new[] that resulted in a crash so I replaced delete[] with delete and it worked. so it has become a bad habit, I have changed my code now so it does delete[] instead of delete.

Quote:

3. Your peek function should probably throw an exception when the heap is empty, just like your dequeue function.


Yes, I have missed that one.

Quote:

4. Your code maintains m_iLastItem as an index to the last item in the heap, instead of one past it, as is done in the STL (for good reason I might add). Thus your for loop in printQueue is wrong. It would need to be:

for( int i=0; i<=m_iLastItem; i++ )


I had m_iNextItem before but I changed so I missed that part, the reason for the change was that I find the code more understanding when having a pointer/index to the last item added rather than the next position.

Quote:

5. Following on from (4), this means that your isFull fucntion has an off by one error because by the time m_iLastItem = m_iMaxSize you have already overflowed the buffer by one element. Thus I'd strongly suggest changing your code so that m_iLastItem stores the index to the item after the last valid item, which has numerous other advantages. Meaning of course, you wouldn't make the change listed in (4), but would modify your constructor, enqueue, dequeue and isEmpty functions.


what are the advantages of having an index to the next empty position than having one to the last inserted position?

[Edited by - McZ on December 18, 2005 2:47:43 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.