jutil
Class BinaryHeap

java.lang.Object
  jutil.BinaryHeap

All Implemented Interfaces:

java.io.Serializable, PriorityQueue

public class BinaryHeap
extends java.lang.Object
implements PriorityQueue

A binary heap is a complete binary tree except possibly for the bottom level. The element of every node is greater than the element of its parent. Thus, the smallest element is stored at the root of the tree.

See Also:

Serialized Form

Field Summary

private int	capacity The capacity of the heap is a power of 2.
private java.lang.Comparable[]	elems The children of elems[i] are stored in elems[2i] and elems[2i + 1], the root (= min) is in elems[1].
private int	size The number of elements stored.

Constructor Summary

BinaryHeap()
Initializes capacity to 2^8 = 512.

BinaryHeap(int exp)
Initializes capacity to 2^exp.

Method Summary

void	clear() Sets elems[i] to null for each i.
java.lang.Comparable	deleteMin() Removes and returns the smallest element.
void	insert(java.lang.Comparable x) Inserts element according to its natural order.
boolean	isEmpty() Returns true if size is 0.
private void	percolateDown(int hole) A helper method that repeatedly swaps a node with its smaller child until there are no smaller children.
int	size() Returns the size of the heap.
java.lang.Comparable[]	toArray() Converts heap into a sorted array.
java.lang.String	toString() Converts heap into a LISP-style string representation of a heap.
private java.lang.String	toString(int i) Recursively converts the heap rooted at element i into a LISP style string representation of a tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

elems

private java.lang.Comparable[] elems

The children of elems[i] are stored in elems[2i] and elems[2i + 1], the root (= min) is in elems[1].

size

private int size

The number of elements stored.

capacity

private int capacity

The capacity of the heap is a power of 2.

Constructor Detail

BinaryHeap

public BinaryHeap(int exp)

Initializes capacity to 2^exp.

BinaryHeap

public BinaryHeap()

Initializes capacity to 2^8 = 512.

Method Detail

clear

public void clear()

Sets elems[i] to null for each i.

Specified by:

clear in interface PriorityQueue

size

public int size()

Returns the size of the heap.

Specified by:

size in interface PriorityQueue

Returns:

The number of non-null elements.

isEmpty

public boolean isEmpty()

Returns true if size is 0.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if size = 0.

toString

public java.lang.String toString()

Converts heap into a LISP-style string representation of a heap. Use toArray if this is too confusing.

Overrides:

toString in class java.lang.Object

toString

private java.lang.String toString(int i)

Recursively converts the heap rooted at element i into a LISP style string representation of a tree.

toArray

public java.lang.Comparable[] toArray()

Converts heap into a sorted array. Caution: array order may not reflect. Caution: this method is inefficient. heap order in the case of equal items.

Returns:

the heap as a sorted array.

insert

public void insert(java.lang.Comparable x)
            throws OverflowException

Inserts element according to its natural order. The algorithm inserts x at the bottom of the tree, then repeatedly swaps x with its parent until a smaller parent is encountered.

Specified by:

insert in interface PriorityQueue

Parameters:

x - element to be inserted.

Throws:

OverflowException - if the heap is full.

deleteMin

public java.lang.Comparable deleteMin()

Removes and returns the smallest element. After elems[1] is removed, the largest element moves to the root and then percolates down to its new position.

Specified by:

deleteMin in interface PriorityQueue

Returns:

null if the tree is empty, elems[1] otherwise.

percolateDown

private void percolateDown(int hole)

A helper method that repeatedly swaps a node with its smaller child until there are no smaller children.

Parameters:

hole - position of the element to percolate down.