Priority queue collection class

Posted: 07/20/07 19: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: 08/13/07 07: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.