Algorithm
Development Kit 1.0

algs.model.heap
Class BinaryHeap<E extends java.lang.Comparable<E>>

java.lang.Object
  extended by algs.model.heap.BinaryHeap<E>
Type Parameters:
E - Type of entity to insert into Heap, which must provide Comparable

public class BinaryHeap<E extends java.lang.Comparable<E>>
extends java.lang.Object

A Binary Heap that can be used as a Priority Queue since it enables elements to have its priority updated while in queue.

The elements in the queue have an integer ID and given PRIORITY.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
BinaryHeap(int n)
          Construct Binary Heap of the given size.
 
Method Summary
 void decreaseKey(int id, java.lang.Comparable<E> reducedPriority)
          Decrease the priority of the known element in the Binary Heap with the given identifier.
 void insert(int id, java.lang.Comparable<E> priority)
          Insert the element (id) with given priority.
 boolean isEmpty()
          Determines if Binary Heap is empty.
 java.lang.Comparable<E> smallest()
          Return the PRIORITY of the smallest entry.
 int smallestID()
          Return the integer IDENTIFIER of the smallest entry.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BinaryHeap

public BinaryHeap(int n)
Construct Binary Heap of the given size.

Since we cannot parameterize Element[] construction, this method suppresses warnings.

Parameters:
n - size of array.
Method Detail

isEmpty

public boolean isEmpty()
Determines if Binary Heap is empty.


smallest

public java.lang.Comparable<E> smallest()
Return the PRIORITY of the smallest entry.


smallestID

public int smallestID()
Return the integer IDENTIFIER of the smallest entry.


insert

public void insert(int id,
                   java.lang.Comparable<E> priority)
Insert the element (id) with given priority.

Inserting too many items into a Binary Heap will cause exception.

Parameters:
id -
priority -

decreaseKey

public void decreaseKey(int id,
                        java.lang.Comparable<E> reducedPriority)
Decrease the priority of the known element in the Binary Heap with the given identifier.

No check is done to see if the new "reducedPriority" is in fact actually less than the actual priority of the element in the Binary Heap. Be careful that you only call with proper smaller element.

Parameters:
id -
reducedPriority -

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.