Sunday, December 16, 2012

Binary Heaps - part two

So, let's go ahead and flesh out the BinaryHeap abstract class I put together in the last post.  You'll notice a few things have changed.  For one, I've decided to make heapify a private method.  I was thinking about potential DRY violations in MinHeap and MaxHeap implementations.  The heapify methods will be identical except for how we treat the return value of the compareTo methods.  The BinaryHeap abstract class's constructors now require a sign argument - this will be the value against which those return values will be compared.

I've also added a constructor that takes the contents of a Java Collection and adds it to the heap en masse, for convenience and efficiency.

Something to remember here when implementing remove: make sure that the last element of the heap is added to the top of the heap, not swapped with that element.  Using swap is almost guaranteed to break the heap property constraint!  This took me a while to debug.


No comments:

Post a Comment