Heaps
are full binary trees (not BST). If the bottom level is not full, the elements
are to the left.last updated 11/9/05
Only the highest-priority element can be accessed
Priority queues are useful for any application that involves processing items by priority
When an item is added to a priority queue, the object is in order by the Comparable characteristic (compareTo definition)--the priority.
A priority queue can be used for sorting purposes as we may see later.
public interface PriQueueInterface
{
public boolean isEmpty();
// Effect: Determines whether this priority queue is empty.
// Postcondition: Return value = (this priority queue is empty)
public boolean isFull();
// Effect: Determines whether this priority queue is full.
// Postcondition: Return value = (priority queue is full)
public void enqueue(Comparable item);
// Effect: Adds item to this priority queue.
// Postcondition: If (this priority queue is full)
// an unchecked exception that communicates ‘enqueue
// on priority queue full’ is thrown
// Else
// item is in this priority queue.
public Comparable dequeue();
// Effect: Removes element with highest priority from this
// priority queue and returns a reference to it
// Postconditions: If (this priority queue is empty)
// an unchecked exception that communicates ‘dequeue
// on empty priority queue’ is thrown
// Else
// Highest priority element has been removed.
// Return value = (reference to the removed element)
}
There are many ways to implement a priority queue
An unsorted List- dequeuing would require searching through the entire list O(N); enqueuing would be O(1)
An Array-Based Sorted List- Enqueuing is expensive O(N); dequeuing would also be O(N)
A Reference-Based Sorted List- Enqueuing again is O(N); dequeuing would be O(1)
A Binary Search Tree- On average, O(log2N) steps for both enqueue and dequeue, but can degenerate into a linked list for a worst case O(N) performance
The heap guarantees O(log2N) steps, even in the worst case
An implementation of a Priority Queue based on a complete binary tree, each of whose elements contains a value that is greater than or equal to the value of its children.
Heaps
are full binary trees (not BST). If the bottom level is not full, the elements
are to the left.
Heaps are typically implemented as an array using the parent-child computation described earlier. Given an arbitrary position p, you can calculate its parent, left child and right child, left and right siblings:
parent = (p-1)/2
leftSibling = i-1
rightSibling = i+1
leftChild = i*2+1
rightChild = i*2+2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| A | B | C | E | G | K | M | Q | W |
ReheapUp -- add the new item to the first empty leaf at the bottom level and re-establish the heap characteristic by swapping with the parent if the child should be a the new parent. Repeat upward until the root is reached or no swap is necessary
Used when enqueuing.
ReheapDown -- the root is removed (dequeued) and then the heap is re-established by pulling upward the child that has the largest priority. Repeat until no shift upward is necessary or the leaf is reached. Use the rightmost, bottom level value as the fill-in.
public class Heap implements PriQueueInterface
{
private Comparable[] elements; // Array that holds priority queue elements
private int lastIndex; // index of last element in priority queue
private int maxIndex; // index of last position in array
// Constructor
public Heap(int maxSize)
{
elements = new Comparable[maxSize];
lastIndex = -1;
maxIndex = maxSize - 1;
}
public boolean isEmpty()
// Determines whether this priority queue is empty.
{
return (lastIndex == -1);
}
public boolean isFull()
// Determines whether this priority queue is full.
{
return (lastIndex == maxIndex);
}
private void reheapUp(Comparable item)
// Current lastIndex position is empty
// Inserts item into the tree and ensures shape and order properties
{
int hole = lastIndex;
while ((hole > 0) // hole is not root
&& // short circuit
(item.compareTo(elements[(hole - 1) / 2]) > 0)) // item > hole's parent
{
elements[hole] = elements[(hole - 1) / 2]; // move hole's parent down
hole = (hole - 1) / 2; // move hole up
}
elements[hole] = item; // place item into final hole
}
public void enqueue(Comparable item) throws PriQOverflowException
// Adds item to this priority queue.
// Throws PriQOverflowException if priority queue already full
{
if (lastIndex == maxIndex)
throw new PriQOverflowException("Priority queue is full");
else
{
lastIndex = lastIndex + 1;
reheapUp(item);
}
}
private int newHole(int hole, Comparable item)
// If either child of hole is larger than item this returns the index
// of the larger child; otherwise it returns the index of hole
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else
if (left == lastIndex)
// hole has left child only
if (item.compareTo(elements[left]) < 0)
// item < left child
return left;
else
// item >= left child
return hole;
else
// hole has two children
if (elements[left].compareTo(elements[right]) < 0)
// left child < right child
if (elements[right].compareTo(item) <= 0)
// right child <= item
return hole;
else
// item < right child
return right;
else
// left child >= right child
if (elements[left].compareTo(item) <= 0)
// left child <= item
return hole;
else
// item < left child
return left;
}
private void reheapDown(Comparable item)
// Current root position is "empty";
// Inserts item into the tree and ensures shape and order properties
{
int hole = 0; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, item); // find next hole
while (newhole != hole)
{
elements[hole] = elements[newhole]; // move element up
hole = newhole; // move hole down
newhole = newHole(hole, item); // find next hole
}
elements[hole] = item; // fill in the final hole
}
public Comparable dequeue() throws PriQUnderflowException
// Removes element with highest priotity from this priority queue
// and returns a reference to it.
// Throws PriQUnderflowException if priority queue is empty.
{
Comparable hold; // item to be dequeued and returned
Comparable toMove; // item to move down heap
if (lastIndex == -1)
throw new PriQUnderflowException("Priority queue is empty");
else
{
hold = elements[0]; // remember item to be returned
toMove = elements[lastIndex]; // item to reheap down
lastIndex = lastIndex - 1; // decrease priority queue size
reheapDown(toMove); // rstore heap properties
return hold; // return largest element
}
}
public String toString()
// returns a string of all the heap elements
{
String theHeap = new String("the heap is:\n");
for (int index = 0; index <= lastIndex; index++)
theHeap = theHeap + index + ". " + elements[index] + "\n";
return theHeap;
}
}