Archived

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

q2guy

problems with a min binary heap (java)

Recommended Posts

q2guy    122
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