Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

q2guy

problems with a min binary heap (java)

This topic is 5462 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have implemented a min binary heap in java to make a priority queue in which first element is the node with lowest f member variable value (double f. But, the result is a not perfect sorted list, usually the first 10 elements are good sorted, but not all list are good sorted, I post my push and pop functions, if anyone find the errors, please tell me! Thanx !
void push(NODE x)
{
	int i;
	boolean end=false;
	
	v[index] = x;
	
	i = index;
	
	while (!end && (i >> 1) != 0)
	{
		if (v[i].f < v[i>>1].f)
			swap_by_index(i,(i>>1));

		i = i>>1;
		
		if (i <= 1) 
			end = true;
		else 
			end = false;
	}
	
	index++;
	index2 = index;	
}

NODE pop()
{
	boolean end=false;
	int i;
	
	NODE result = v[1];

	if (index >= 1)
	{
		v[1] = v[index-1];
		index--;

		i = 1;
		
		while (((i*2 <= index) || (i*2+1 <= index)) && !end)
		{
			if ((v[i].f > v[i*2].f) || (v[i].f > v[i*2+1].f))
			{
				if (v[i*2].f < v[i*2+1].f)
					swap_by_index(i,(i*2));
				else if (v[i*2].f > v[i*2+1].f)
					swap_by_index(i,(i*2+1));
				else 
					end=true;

				i*=2;
			}
			else end=true;
		}
	}

	return result;
}
// swap_by_index swaps two elements pointed by indexes in array v[] (the queue)

// index is the size of the array, array begins in position 1, v[1] in which can be at the end the node with lowest f value

[edited by - q2guy on August 7, 2003 1:22:19 PM]

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!