com.mhhe.clrs2e
Class MaxHeapPriorityQueue

java.lang.Object
  |
  +--com.mhhe.clrs2e.Heap
        |
        +--com.mhhe.clrs2e.MaxHeap
              |
              +--com.mhhe.clrs2e.MaxHeapPriorityQueue

All Implemented Interfaces:

MaxPriorityQueue

public class MaxHeapPriorityQueue

extends MaxHeap

implements MaxPriorityQueue

Implements a max-priority queue by a max-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

MaxHeapPriorityQueue()
Creates an empty max-priority queue.

Method Summary

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

Methods inherited from class com.mhhe.clrs2e.MaxHeap

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.MaxPriorityQueue

isEmpty

Constructor Detail

MaxHeapPriorityQueue

public MaxHeapPriorityQueue()

Creates an empty max-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 max-priority queue.

Specified by:

insert in interface MaxPriorityQueue

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 an increaseKey(java.lang.Object, java.lang.Comparable) operation.

maximum

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

Returns the largest element in the max-priority queue without removing the element.

Specified by:

maximum in interface MaxPriorityQueue

Throws:

HeapUnderflowException - if the max-priority queue is empty.

extractMax

public com.mhhe.clrs2e.DynamicSetElement extractMax()

Removes and returns the largest element in the max-priority queue.

In order for the handle of the element returned to be eligible for garbage collection, the user of the MaxPriorityQueue 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 extractMax.

Specified by:

extractMax in interface MaxPriorityQueue

Throws:

HeapUnderflowException - if the max-priority queue is empty.

increaseKey

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

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

Specified by:

increaseKey in interface MaxPriorityQueue

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 less 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 less than or equal to its parent.

Parameters:

i - Index of the element to bubble up.