MinHeap.java
// TODO: Reorganize the code so that the 0 entry of the array is not wasted.
import java.util.*;
/**
This class implements a heap.
*/
public class MinHeap
{
private ArrayList<Comparable> elements;
/**
Constructs an empty heap.
*/
public MinHeap()
{
elements = new ArrayList<Comparable>();
elements.add(null);
}
/**
Adds a new element to this heap.
@param newElement the element to add
*/
public void add(Comparable newElement)
{
// Add a new leaf
elements.add(null);
int index = elements.size() - 1;
// Demote parents that are larger than the new element
while (index > 1
&& getParent(index).compareTo(newElement) > 0)
{
elements.set(index, getParent(index));
index = getParentIndex(index);
}
// Store the new element into the vacant slot
elements.set(index, newElement);
}
/**
Gets the minimum element stored in this heap.
@return the minimum element
*/
public Comparable peek()
{
return elements.get(1);
}
/**
Removes the minimum element from this heap.
@return the minimum element
*/
public Comparable remove()
{
Comparable minimum = elements.get(1);
// Remove last element
int lastIndex = elements.size() - 1;
Comparable last = elements.remove(lastIndex);
if (lastIndex > 1)
{
elements.set(1, last);
fixHeap();
}
return minimum;
}
/**
Turns the tree back into a heap, provided only the root
node violates the heap condition.
*/
private void fixHeap()
{
Comparable root = elements.get(1);
int lastIndex = elements.size() - 1;
// Promote children of removed root while they are larger than last
int index = 1;
boolean more = true;
while (more)
{
int childIndex = getLeftChildIndex(index);
if (childIndex <= lastIndex)
{
// Get smaller child
// Get left child first
Comparable child = getLeftChild(index);
// Use right child instead if it is smaller
if (getRightChildIndex(index) <= lastIndex
&& getRightChild(index).compareTo(child) < 0)
{
childIndex = getRightChildIndex(index);
child = getRightChild(index);
}
// Check if larger child is smaller than root
if (child.compareTo(root) < 0)
{
// Promote child
elements.set(index, child);
index = childIndex;
}
else
{
// Root is smaller than both children
more = false;
}
}
else
{
// No children
more = false;
}
}
// Store root element in vacant slot
elements.set(index, root);
}
/**
Returns the number of elements in this heap.
*/
public int size()
{
return elements.size() - 1;
}
/**
Returns the index of the left child.
@param index the index of a node in this heap
@return the index of the left child of the given node
*/
private static int getLeftChildIndex(int index)
{
return 2 * index;
}
/**
Returns the index of the right child.
@param index the index of a node in this heap
@return the index of the right child of the given node
*/
private static int getRightChildIndex(int index)
{
return 2 * index + 1;
}
/**
Returns the index of the parent.
@param index the index of a node in this heap
@return the index of the parent of the given node
*/
private static int getParentIndex(int index)
{
return index / 2;
}
/**
Returns the value of the left child.
@param index the index of a node in this heap
@return the value of the left child of the given node
*/
private Comparable getLeftChild(int index)
{
return elements.get(2 * index);
}
/**
Returns the value of the right child.
@param index the index of a node in this heap
@return the value of the right child of the given node
*/
private Comparable getRightChild(int index)
{
return elements.get(2 * index + 1);
}
/**
Returns the value of the parent.
@param index the index of a node in this heap
@return the value of the parent of the given node
*/
private Comparable getParent(int index)
{
return elements.get(index / 2);
}
}
Use the following files:
HeapDemo.java
/**
This program demonstrates the use of a heap as a priority queue.
*/
public class HeapDemo
{
public static void main(String[] args)
{
MinHeap q = new MinHeap();
q.add(new WorkOrder(3, "Shampoo carpets"));
q.add(new WorkOrder(7, "Empty trash"));
q.add(new WorkOrder(8, "Water plants"));
q.add(new WorkOrder(10, "Remove pencil sharpener shavings"));
q.add(new WorkOrder(6, "Replace light bulb"));
q.add(new WorkOrder(1, "Fix broken sink"));
q.add(new WorkOrder(9, "Clean coffee maker"));
q.add(new WorkOrder(2, "Order cleaning supplies"));
while (q.size() > 0)
System.out.println(q.remove());
}
}
WorkOrder.java
/**
This class encapsulates a work order with a priority.
*/
public class WorkOrder implements Comparable
{
private int priority;
private String description;
/**
Constructs a work order with a given priority and description.
@param aPriority the priority of this work order
@param aDescription the description of this work order
*/
public WorkOrder(int aPriority, String aDescription)
{
priority = aPriority;
description = aDescription;
}
public String toString()
{
return "priority=" + priority + ", description=" + description;
}
public int compareTo(Object otherObject)
{
WorkOrder other = (WorkOrder) otherObject;
if (priority < other.priority) return -1;
if (priority > other.priority) return 1;
return 0;
}
}