Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Priority queue collection class

Moderators: kris

Posted: 07/20/07 10:15:38

Fairly simple to implement (using a heap) and can be extremely useful. I might be able to do some development work on this next week if I have the spare time and there is any interest. Thoughts, anyone?

Author Message

Posted: 07/20/07 23:40:19

It would be nice to have a general container, but there are heap routines in tango.core.Array already, if someone needs them. Look for makeHeap, pushHeap, popHeap, and sortHeap.

Posted: 07/25/07 20:20:32

JaredMoore wrote:

Fairly simple to implement (using a heap) and can be extremely useful. I might be able to do some development work on this next week if I have the spare time and there is any interest. Thoughts, anyone?

Sounds interesting ... any more details?

Posted: 08/13/07 11:12:52

Here's an old binary heap of mine which works as a priority queue. I wrote it over a year ago (meaning 1. it might not work properly with the current DMD, 2. it uses Phobos, and 3. the code could be improved in terms of speed and clarity) and haven't used it in about equally long a time, but it should work. I used it as a min-heap in an A* pathfinder, holding graph nodes.

class BinaryHeap(TYPE) {
	private void init(HeapType t)
	in {
		assert (t != HeapType.TYPELESS);
	} body {
		if (t == HeapType.MIN_HEAP) {
			this.func = function int(TYPE a, TYPE b) { return a < b; };
			alias first smallest;
			alias first minimum;
		} else if (t == HeapType.MAX_HEAP) {
			this.func = function int(TYPE a, TYPE b) { return a > b; };
			alias first largest;
			alias first maximum;
		} else
			throw new Exception("What kind of HeapType is that supposed to be?");

		this.type = t;
	}
public:
	this(HeapType t, TYPE[] a...) {
		init(t);

		if (a.length > 0) {
			arr = a.dup;
			for (size_t i = a.length / 2; i > 0; --i)
				this.heapify(i-1);
		}
	}
	this(BinaryHeap a, BinaryHeap b, HeapType t = HeapType.TYPELESS) {
		if (t == HeapType.TYPELESS)
			t = a.type;

		init(t);

		arr = a.array.dup ~ b.array.dup;
		for (size_t i = arr.length / 2; i > 0; --i)
			this.heapify(i-1);
	}

	void heapify(size_t pos)
	in {
		assert (pos < arr.length);
	} body {
		size_t left  = left(pos),
		       right = right(pos),
		       needsMoving = pos;

		if (left < arr.length && func(arr[left], arr[pos]))
			needsMoving = left;
		if (right < arr.length && func(arr[right], arr[needsMoving]))
			needsMoving = right;

		if (needsMoving != pos) {
			this.swap(pos, needsMoving);
			this.heapify(needsMoving);
		}
	}

	TYPE pop()
	in {
		assert (arr.length >= 1);
	} body {
		if (arr.length == 1) {
			TYPE val = arr[0];
			arr.length = arr.length - 1;
			return val;
		}

		TYPE returnVal = arr[0];

		arr[0] = arr[arr.length - 1];
		arr.length = arr.length - 1;
		this.heapify(0);

		return returnVal;
	}

	void replace(size_t i, TYPE val) {
		if (val == arr[i])
			return;

		if (func(arr[i], val)) {
			char[] error = std.string.format("Cannot replace a key in a %s-binary heap with a %s one!",
			                                 type == HeapType.MIN_HEAP ? "min" : "max",
			                                 type == HeapType.MIN_HEAP ? "larger" : "smaller");
			throw new Exception(error);
		}
		
		doReplace(i, val);
	}

	void insert(TYPE t) {
		size_t i = arr.length;
		arr.length = arr.length + 1;

		doReplace(i, t);
	}
	alias insert put;
	alias insert push;

	size_t length() { return arr.length; }

	TYPE[] array() { return arr; }
	TYPE   first() in { assert(arr.length > 0); } body { return arr[0]; }
	alias first top;
	alias first head;
private:
	TYPE[] arr;
	int function(TYPE, TYPE) func;
	HeapType type;

	size_t parent(size_t i) { return (i-1)/2; }
	size_t left  (size_t i) { return 2*i+1;   }
	size_t right (size_t i) { return 2*i+2;   }
	void swap(size_t a, size_t b) {
		TYPE t = arr[a];
		arr[a] = arr[b];
		arr[b] = t;
	}
	
	void doReplace(size_t i, TYPE val) {
		arr[i] = val;
		while (i > 0 && func(arr[i], arr[parent(i)])) {
			this.swap(i, parent(i));
			i = parent(i);
		}
	}

	unittest {
		// mostly checking the heap property:
		// for max-heaps, a[i] < a[parent(i)]
		// for min-heaps, a[i] > a[parent(i)]
		// where parent(i) is, with zero-indexed arrays, (i-1)/2

		// this is already a binary heap
		// make sure that heapifying doesn't break or needlessly change an old binary heap...
		const int[] array = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1];
		auto heap = new BinaryHeap!(int)(HeapType.MAX_HEAP, array);
		assert (heap.array.length == array.length);
		foreach (size_t i, int v; heap.array)
			assert (v == array[i]);

		// make sure that replacing with an already-correct one doesn't change anything...
		heap.replace(1, 15);
		assert (heap.array[0] == 16);
		assert (heap.array[1] == 15);
		assert (heap.array[2] == 10);
		assert (heap.array[3] == 8);
		assert (heap.array[4] == 7);
		assert (heap.array[5] == 9);
		assert (heap.array[6] == 3);
		assert (heap.array[7] == 2);
		assert (heap.array[8] == 4);
		assert (heap.array[9] == 1);

		// make sure that the heapify method works...
		const int[] brray = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1];
		heap = new BinaryHeap!(int)(HeapType.MAX_HEAP, brray);
		heap.heapify(1);
		assert (heap.array.length == brray.length);
		foreach (size_t i, int v; heap.array)
			if ((i-1)/2 >= 0 && (i-1)/2 < heap.array.length)
				assert (v < heap.array[(i-1)/2]);

		// make sure that can construct a heap from an unordered array properly...
		const int[] crray = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
		heap = new BinaryHeap!(int)(HeapType.MAX_HEAP, crray);
		assert (heap.array.length == crray.length);
		foreach (size_t i, int v; heap.array)
			if ((i-1)/2 >= 0 && (i-1)/2 < heap.array.length)
				assert (v < heap.array[(i-1)/2]);

		// and again...
		int[] drray = array.dup.reverse;
		heap = new BinaryHeap!(int)(HeapType.MAX_HEAP, drray);
		assert (heap.array.length == drray.length);
		foreach (size_t i, int v; heap.array)
			if ((i-1)/2 >= 0 && (i-1)/2 < heap.array.length)
				assert (v < heap.array[(i-1)/2]);
	}
}

Feel free to port it to Tango (and place it in, even) if you like, but I'd personally like to see something more efficient, such as a Pairing heap or Splay heap, in Tango.

See the paper Experimental Study of High Performance Priority Queues which offers many even faster heaps. However, in order to squeeze speed they don't support the handy decrease-key operation, and some don't support delete. If you or someone wants to whip one up, go ahead, but I'd prefer one of the traditional heaps mentioned in secion 3.1 of the paper, due to their versatility.

Posted: 03/30/08 21:22:14

Deewiant wrote:

Here's an old binary heap of mine which works as a priority queue.

I need to implement a priority queue heap for Blaze's continuous collision detection scheme, and was wondering if anyone would be willing the help me in this endeavor.

Basically, I need to store and sort all (potential) dynamic collision events detected during a time step based on time of impact (TOI). For all potentially colliding objects, the TOI and contact information needs to be stored in a list. Objects may have more than one potential contact. If two rigid bodies collide, all future collision events (collisions with a greater TOI) involving either one of the two bodies need to be invalidated.

I've found a C++ implementation, and may need help integrating into Blaze: http://idav.ucdavis.edu/~okreylos/ResDev/Balls/index.html

Any help/thoughts/suggestions would be greatly appreciated!

Best regards,
Mason