com.mhhe.clrs2e
Class Heap

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

Direct Known Subclasses:

MaxHeap, MinHeap

public abstract class Heap

extends java.lang.Object

Abstract base class for both binary min-heaps and binary max-heaps. Implements methods common to both, based on Chapter 6 of Introduction to Algorithms, Second edition. Objects in the heap must implement the Comparable interface.

All operations in this class maintain the invariant that the heap has the heap property.

Subclasses must implement heapify(int) to be concrete. Extended by MinHeap and MaxHeap.

Nested Class Summary

protected static class	Heap.Handle Nested class for handles within a heap.
class	Heap.Heapsort Implements the Sorter interface via heapsort.

Field Summary

protected java.lang.Comparable[]	array The array holding the heap.
protected int	heapSize How many elements are actually in the heap.

Constructor Summary

Heap()
Creates an empty heap.

Heap(java.lang.Comparable[] array)
Makes a heap in place from the argument, and ensures that the heap property holds.

Method Summary

void	buildHeap() Rearranges the array within the heap so that it complies with the heap property.
protected void	exchange(int i, int j) Swaps the elements at two indices.
java.lang.Comparable	head() Returns the first element in the heap without removing it.
abstract void	heapify(int i) Restores the heap property.
boolean	isEmpty() Returns true if the heap is empty, false otherwise.
static int	left(int i) Returns the index of the left child of a node.
com.mhhe.clrs2e.Sorter	makeSorter() Returns a Heap.Heapsort object that will sort this heap.
static int	parent(int i) Returns the index of the parent of a node.
static int	right(int i) Returns the index of the right child of a node.

Methods inherited from class java.lang.Object

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

Field Detail

array

protected java.lang.Comparable[] array

The array holding the heap.

heapSize

protected int heapSize

How many elements are actually in the heap.

Constructor Detail

Heap

public Heap()

Creates an empty heap.

Heap

public Heap(java.lang.Comparable[] array)

Makes a heap in place from the argument, and ensures that the heap property holds.

Parameters:

array - Array from which a heap is made.

Method Detail

heapify

public abstract void heapify(int i)

Restores the heap property. Assumes that at the time of call, the heap property holds everywhere, with the possible exception of one position and its children. Must be implemented in subclasses.

Parameters:

i - Index of the position at which the heap property might not hold.

exchange

protected void exchange(int i,
                        int j)

Swaps the elements at two indices.

Parameters:

i - One index.

j - The other index.

parent

public static final int parent(int i)

Returns the index of the parent of a node.

Parameters:

i - The node whose parent's index is returned.

left

public static final int left(int i)

Returns the index of the left child of a node.

Parameters:

i - The node whose left child's index is returned.

right

public static final int right(int i)

Returns the index of the right child of a node.

Parameters:

i - The node whose right child's index is returned.

isEmpty

public final boolean isEmpty()

Returns true if the heap is empty, false otherwise.

head

public java.lang.Comparable head()

Returns the first element in the heap without removing it. For a max-heap, the largest element, and for a min-heap, the smallest element.

buildHeap

public void buildHeap()

Rearranges the array within the heap so that it complies with the heap property.

makeSorter

public com.mhhe.clrs2e.Sorter makeSorter()

Returns a Heap.Heapsort object that will sort this heap.