Complete BinaryHeap Implementation
Now we'll put all the pieces together into a complete, production-ready BinaryHeap class.
The PriorityQueue Interface
First, let's define the interface from Day 41:
Java
public interface PriorityQueue<T extends Comparable<T>> {
/**
* Insert an item into the priority queue.
* @param item the item to insert
*/
void insert(T item);
/**
* Get the highest-priority item without removing it.
* @return the highest-priority item
* @throws EmptyPriorityQueueException if empty
*/
T best();
/**
* Remove and return the highest-priority item.
* @return the highest-priority item
* @throws EmptyPriorityQueueException if empty
*/
T remove();
/**
* Check if the priority queue is empty.
* @return true if empty, false otherwise
*/
boolean isEmpty();
/**
* Get the number of items in the priority queue.
* @return the size
*/
int size();
}
The Custom Exception
Java
public class EmptyPriorityQueueException extends RuntimeException {
public EmptyPriorityQueueException(String message) {
super(message);
}
}
Complete BinaryHeap Implementation
Java
import java.util.Comparator;
public class BinaryHeap<T extends Comparable<T>> implements PriorityQueue<T> {
private static final int DEFAULT_CAPACITY = 10;
private T[] heap;
private int size;
private Comparator<T> comparator;
/**
* Constructor using natural ordering (Comparable).
*/
public BinaryHeap() {
this(null);
}
/**
* Constructor using custom comparator.
* @param comparator the comparator to use for ordering, or null for natural ordering
*/
@SuppressWarnings("unchecked")
public BinaryHeap(Comparator<T> comparator) {
this.heap = (T[]) new Comparable[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
@Override
public void insert(T item) {
if (item == null) {
throw new IllegalArgumentException("Cannot insert null into priority queue");
}
// Resize if necessary
if (size == heap.length) {
resize();
}
// Add item at next available position
heap[size] = item;
size++;
// Restore heap property
bubbleUp(size - 1);
}
@Override
public T best() {
if (isEmpty()) {
throw new EmptyPriorityQueueException("Cannot access best from empty priority queue");
}
return heap[0];
}
@Override
public T remove() {
if (isEmpty()) {
throw new EmptyPriorityQueueException("Cannot remove from empty priority queue");
}
// Save root to return
T root = heap[0];
// Replace root with last element
heap[0] = heap[size - 1];
heap[size - 1] = null; // Help garbage collection
size--;
// Restore heap property (if heap is not empty)
if (size > 0) {
bubbleDown(0);
}
return root;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
// ==================== Private Helper Methods ====================
/**
* Bubble up the element at the given index to restore heap property.
* @param index the index to start bubbling up from
*/
private void bubbleUp(int index) {
int parentIndex = parentIndex(index);
while (index > 0 && compare(heap[index], heap[parentIndex]) > 0) {
swap(index, parentIndex);
index = parentIndex;
parentIndex = parentIndex(index);
}
}
/**
* Bubble down the element at the given index to restore heap property.
* @param index the index to start bubbling down from
*/
private void bubbleDown(int index) {
while (hasLeft(index)) {
// Find the larger child
int largerChildIndex = leftIndex(index);
if (hasRight(index) &&
compare(heap[rightIndex(index)], heap[largerChildIndex]) > 0) {
largerChildIndex = rightIndex(index);
}
// Check if heap property is satisfied
if (compare(heap[index], heap[largerChildIndex]) >= 0) {
break; // Parent >= larger child, done
}
// Swap with larger child
swap(index, largerChildIndex);
index = largerChildIndex;
}
}
/**
* Compare two elements using the comparator or natural ordering.
* @param a first element
* @param b second element
* @return positive if a > b, negative if a < b, zero if equal
*/
private int compare(T a, T b) {
if (comparator != null) {
return comparator.compare(a, b);
} else {
return a.compareTo(b);
}
}
/**
* Swap elements at two indices.
* @param i first index
* @param j second index
*/
private void swap(int i, int j) {
T temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
/**
* Resize the internal array to double its current capacity.
*/
@SuppressWarnings("unchecked")
private void resize() {
T[] newHeap = (T[]) new Comparable[heap.length * 2];
System.arraycopy(heap, 0, newHeap, 0, size);
heap = newHeap;
}
// ==================== Index Calculation Methods ====================
/**
* Get the index of the parent of the node at the given index.
* @param index the child index
* @return the parent index
*/
private int parentIndex(int index) {
return (index - 1) / 2;
}
/**
* Get the index of the left child of the node at the given index.
* @param index the parent index
* @return the left child index
*/
private int leftIndex(int index) {
return 2 * index + 1;
}
/**
* Get the index of the right child of the node at the given index.
* @param index the parent index
* @return the right child index
*/
private int rightIndex(int index) {
return 2 * index + 2;
}
/**
* Check if the node at the given index has a left child.
* @param index the parent index
* @return true if left child exists
*/
private boolean hasLeft(int index) {
return leftIndex(index) < size;
}
/**
* Check if the node at the given index has a right child.
* @param index the parent index
* @return true if right child exists
*/
private boolean hasRight(int index) {
return rightIndex(index) < size;
}
}
Key Implementation Details
1. Dynamic Array Resizing
When the array is full, we double its capacity:
Java
private void resize() {
T[] newHeap = (T[]) new Comparable[heap.length * 2];
System.arraycopy(heap, 0, newHeap, 0, size);
heap = newHeap;
}
Amortized O(log n) insertion: doubling ensures that resize operations are rare enough to maintain O(log n) amortized cost.
2. Null Handling
Java
if (item == null) {
throw new IllegalArgumentException("Cannot insert null into priority queue");
}
Why reject null? Null values can't be compared using compareTo() or most comparators, leading to NullPointerException.
3. Garbage Collection Help
Java
heap[size - 1] = null; // After moving element to root
Setting removed references to null helps the garbage collector reclaim memory faster.
4. Generic Array Creation
Java
@SuppressWarnings("unchecked")
this.heap = (T[]) new Comparable[DEFAULT_CAPACITY];
Java doesn't allow new T[] due to type erasure. We create Comparable[] and cast, suppressing the unchecked warning since we control all insertions.
5. Comparator Support
Java
private Comparator<T> comparator; // Optional comparator
Notice the pattern we used by allowing a non-default constructor that accepts a Comparator<T>:
Java
// Default constructor
public BinaryHeap() {
this(null);
}
// Non-default constructor
public BinaryHeap(Comparator<T> comparator) {
this.heap = (T[]) new Comparable[10];
this.size = 0;
this.comparator = comparator;
}
Finally, we created a compare(a, b) helper method to centralize comparison logic:
Java
private int compare(T a, T b) {
if (comparator != null) {
return comparator.compare(a, b); // Use custom comparator
} else {
return a.compareTo(b); // Use natural ordering
}
}
We will explore how Java's Comparator works and how to use it in the next page.