com.mhhe.clrs2e
Class MinHeapPriorityQueue

java.lang.Object
  |
  +--com.mhhe.clrs2e.Heap
        |
        +--com.mhhe.clrs2e.MinHeap
              |
              +--com.mhhe.clrs2e.MinHeapPriorityQueue

All Implemented Interfaces:

MinPriorityQueue

public class MinHeapPriorityQueue

extends MinHeap

implements MinPriorityQueue

Implements a min-priority queue by a min-heap, based on Chapter 6 of Introduction to Algorithms, Second edition.

Nested Class Summary

Nested classes inherited from class com.mhhe.clrs2e.Heap

Heap.Handle, Heap.Heapsort

Field Summary

Fields inherited from class com.mhhe.clrs2e.Heap

array, heapSize

Constructor Summary

MinHeapPriorityQueue()
Creates an empty min-priority queue.

Method Summary

private void	bubbleUp(int i) Bubbles the element at a given index up in the heap until it is greater than or equal to its parent.
void	decreaseKey(java.lang.Object element, java.lang.Comparable newKey) Decreases the key of a given element to a new value.
protected void	exchange(int i, int j) Overrides the exchange method to update the index part of each Handle.
com.mhhe.clrs2e.DynamicSetElement	extractMin() Removes and returns the smallest element in the min-priority queue.
java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement x) Inserts a dynamic-set element into the min-priority queue.
com.mhhe.clrs2e.DynamicSetElement	minimum() Returns the smallest element in the min-priority queue without removing the element.

Methods inherited from class com.mhhe.clrs2e.MinHeap

heapify

Methods inherited from class com.mhhe.clrs2e.Heap

buildHeap, head, isEmpty, left, makeSorter, parent, right

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.mhhe.clrs2e.MinPriorityQueue

isEmpty

Constructor Detail

MinHeapPriorityQueue

public MinHeapPriorityQueue()

Creates an empty min-priority queue.

Method Detail

exchange

protected void exchange(int i,
                        int j)

Overrides the exchange method to update the index part of each Handle.

Overrides:

exchange in class Heap

Parameters:

i - One index.

j - The other index.

insert

public java.lang.Object insert(com.mhhe.clrs2e.DynamicSetElement x)

Inserts a dynamic-set element into the min-priority queue.

Specified by:

insert in interface MinPriorityQueue

Parameters:

x - The dynamic-set element to be inserted.

Returns:

A handle to the inserted item. This handle is how the item is accessed in a decreaseKey(java.lang.Object, java.lang.Comparable) operation.

minimum

public com.mhhe.clrs2e.DynamicSetElement minimum()
                                          throws HeapUnderflowException

Returns the smallest element in the min-priority queue without removing the element.

Specified by:

minimum in interface MinPriorityQueue

Throws:

HeapUnderflowException - if the min-priority queue is empty.

extractMin

public com.mhhe.clrs2e.DynamicSetElement extractMin()

Removes and returns the smallest element in the min-priority queue.

In order for the handle of the element returned to be eligible for garbage collection, the user of the MinPriorityQueue should include in a DynamicSetElement's satellite data a reference to the handle. This reference should be set to null for the element returned by extractMin.

Specified by:

extractMin in interface MinPriorityQueue

Throws:

HeapUnderflowException - if the min-priority queue is empty.

decreaseKey

public void decreaseKey(java.lang.Object element,
                        java.lang.Comparable newKey)
                 throws KeyUpdateException

Decreases the key of a given element to a new value.

Specified by:

decreaseKey in interface MinPriorityQueue

Parameters:

element - Handle identifying the element; this handle is initially given as the return value of insert(com.mhhe.clrs2e.DynamicSetElement).

newKey - The new key value for this element.

Throws:

KeyUpdateException - if the new key value is greater than the current key value.

bubbleUp

private void bubbleUp(int i)

Bubbles the element at a given index up in the heap until it is greater than or equal to its parent.

Parameters:

i - Index of the element to bubble up.