Binary heaps - part one

As expected, getting started is the hardest part.  After a long day at work (and several loads of laundry,) I thought a bit about the sorts of problems I wanted to attack first.

I've been wanting to review graph algorithms for a while now, specifically shortest path and minimum spanning tree algorithms.  In order to do this, I need to first implement a priority queue-like data structure.  I've read that a number of priority queue implementations are backed by a data structure called a binary heap.  Wikipedia has a fantastic article on them here.

Generally speaking, binary heaps are binary trees that satisfy the following additional constraints:

• They must be complete binary trees.
• They satisfy the heap property.  That is, in the case of max heaps, each node in the tree must have a value greater than or equal to those of its children.  For min heaps, each node in the tree must have a value less than or equal to those of its children.

I didn't have time to produce a full min heap implementation tonight, but I've sketched out an abstract class, BinaryHeap, from which a MinBinaryHeap implementation might inherit.

Given that the heap is a nearly complete binary tree, the data within may be stored in an array (or, in this case, an ArrayList) for nearly optimal compactness.  The left, right, and parent methods return the corresponding array indices for a given input index.  Insert adds a new value to the heap, and delete removes and returns the value at the root of the heap.

The heapify method is particularly important.  It ensures that the subheap at index i satisfies the heap property.

Laundry folded, I'm off to bed.  More tomorrow!