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.

	package heap;
	import java.util.ArrayList;
	import java.util.Collection;
	public abstract class BinaryHeap<T extends Comparable<T>> {
	private ArrayList<T> theHeap;
	private final int sign;
	protected final int left(int i) { return (i << 1) + 1; }
	protected final int right(int i) { return (i << 1) + 2; }
	protected final int parent(int i) { return ((i - 1) >> 1); }
	private void heapify(int i) {
	int j = i;
	int l = left(i);
	int r = right(i);
	if(l < theHeap.size() && (sign == theHeap.get(l).compareTo(theHeap.get(j))))
	j = l;
	if(r < theHeap.size() && (sign == theHeap.get(r).compareTo(theHeap.get(j))))
	j = r;
	if(j != i) {
	swap(i, j);
	heapify(j);
	}
	}
	protected BinaryHeap(int sign) {
	this.sign = sign;
	theHeap = new ArrayList<T>();
	}
	protected BinaryHeap(int sign, Collection<T> contents) {
	this.sign = sign;
	theHeap = new ArrayList<T>(contents);
	for(int i = 1 + theHeap.size() / 2; i >= 0; i--) {
	heapify(i);
	}
	}
	public int size() {
	return theHeap.size();
	}
	private void swap(int i, int j) {
	T temp = theHeap.get(j);
	theHeap.set(j, theHeap.get(i));
	theHeap.set(i, temp);
	}
	public void insert(T t) {
	theHeap.add(t);
	int i = theHeap.size() - 1;
	int p = parent(i);
	while(i > 0 && (sign == theHeap.get(i).compareTo(theHeap.get(p)))) {
	swap(i, p);
	i = p;
	p = parent(i);
	}
	}
	public T remove() {
	T result = null;
	if(theHeap.size() > 0) {
	result = theHeap.remove(0);
	if(theHeap.size() > 1) {
	theHeap.add(0, theHeap.remove(theHeap.size() -1));
	heapify(0);
	}
	}
	return result;
	}
	@Override
	public String toString() {
	return theHeap.toString();
	}
	}

view raw BinaryHeap.java hosted with ❤ by GitHub

	package heap;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	public class MaxHeap<T extends Comparable<T>> extends BinaryHeap<T> {
	public MaxHeap() {
	super(1);
	}
	public MaxHeap(Collection<T> contents) {
	super(1, contents);
	}
	}

view raw MaxHeap.java hosted with ❤ by GitHub

	package heap;
	import java.util.Collection;
	public class MinHeap<T extends Comparable<T>> extends BinaryHeap<T> {
	public MinHeap() {
	super(-1);
	}
	public MinHeap(Collection<T> contents) {
	super(-1, contents);
	}
	}

view raw MinHeap.java hosted with ❤ by GitHub

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.

	package heap;
	import java.util.ArrayList;
	public abstract class BinaryHeap<T extends Comparable<T>> {
	private ArrayList<T> theHeap;
	protected final int left(int i) { return (i << 1) + 1; }
	protected final int right(int i) { return (i << 1) + 2; }
	protected final int parent(int i) { return ((i - 1) >> 1); }
	protected abstract void heapify(int i);
	public BinaryHeap() {
	theHeap = new ArrayList<T>();
	}
	public int size() {
	return theHeap.size();
	}
	public void insert(T t) {
	}
	public T remove() {
	return null;
	}
	}

view raw BinaryHeap.java hosted with ❤ by GitHub

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!

Redy to wenden on my pilgrymage

A grim thought occurred to me about six months ago:

Question: If, as I've often heard, it takes about 10,000 hours of practice to master a skill, what skills have I "mastered?"  

Answer: Do you count surfing the internet and sitting on the couch as skills?  

This bothered me.  A lot.  So, naturally, I planted that thought into the furthest recesses of my mind, poured a bit of gin on it, and went back to the merry task of numbing my brain with cat videos.

Thoughts like these don't die easily, it seems.  They keep bubbling up to the surface of my consciousness, usually late at night, like the demented fever dreams of some Dickensian miser.  

This has got to stop, but how?   

Well, given that I'm supposed to be some kind of programmer (or coder, or developer, or software engineer, or, heaven help you, software architect,) I might as well get better at it.  Why not?  It's a rich field, full of wonderful things to think about.  So, instead of simply going to a programming news aggregator, reading about some fascinating new data structure or algorithm, and promptly returning to the aforementioned cat videos, I'd read a bit more deeply, think about how things might work, put together an implementation, and write about the experience.  In the process, I get to practice coding and writing.

I've decided to manage and share my coding exercises with Github Gists.  Here's an example:

Here's my first github gist. Hopefully, this won't be my last.

view raw FirstStep.txt hosted with ❤ by GitHub

Will I keep this up?  I certainly hope so.  We'll find out tonight.