+--+
| | <--- root
+--+
/ \
/ \
/ \
+ +
/ \ / \
left subtree ---> / \ / \ <--- right subtree
/ \ / \
+-------+ +-------+
|
Definition: The height of an empty (rooted binary) tree is -1. The height of a non-empty (rooted binary) tree is one more than the larger of the heights of its left and right subtrees.
+
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ +-------+
/ |
+-------------+
|
Definition: A max-heap is a complete binary tree satisfying the property that, for any nodes u and v, if u is the parent of v, then the "key value" in u is greater than or equal to the key value in v. (In a min-heap, replace "greater" in the sentence above with "less".)
Max-heaps support only three significant operations:
These operations are analogous to the frontOf(), dequeue(), and enqueue() operations, respectively, on a queue. Indeed, a max-heap is a typical way to implement a priority queue, which is like a standard queue except that the next item to be removed is not the one that was in the queue the longest, but rather the item having highest priority (as measured by the associated key value).
public class MaxHeap<T> {
// class constant
// --------------
private final int DEFAULT_INIT_CAPACITY = 16;
private final int MIN_CAPACITY = 8;
// instance variables
// ------------------
private T[] contents; // array holding elements
private Comparator<T> c;
private int nodeCntr; // # elements in this priority queue
// constructor
// -----------
/* pre: initCapacity > 0 and comp defines a total ordering on
** values of type T.
** post: this max-heapis empty (but with room enough for
** initCapacity elements
*/
public MaxHeap(Comparator<T> comp, int initCapacity) {
this.contents = (T[])(new Object[initCapacity]);
this.nodeCntr = 0;
this.c = comp;
}
/* pre: comp defines a total ordering on values of type T
** post: this max-heap is empty (but with room enough for
** a number of elements equal to a default capacity).
*/
public MaxHeap(Comparator<T> comp)
{ this(comp, DEFAULT_INIT_CAPACITY); }
// observers
// ---------
/* Returns the number of elements in this max-heap.
*/
public int sizeOf() { return nodeCntr; }
/* Reports whether this max-heap is empty.
*/
public boolean isEmtpy() { return sizeOf() == 0; }
/* Returns an element in this max-heap having a key
** value at least as great as every other element.
*/
public int getMax() { return contents[0]; }
// mutators
// --------
/* Inserts the given element into this max-heap.
*/
public void insert(T x) {
if (nodeCntr == contents.length) { // if b is full, double its length
resizeArray(2 * nodeCntr);
}
contents[nodeCntr] = x;
siftUp(nodeCntr);
nodeCntr = nodeCntr + 1;
}
/* Removes the element of this max-heap that would be returned
** by calling getMax(). For convenience, also returns that element.
*/
public T deleteMax() {
T result = getMax();
contents[0] = contents[nodeCntr - 1];
nodeCntr = nodeCntr - 1;
siftDown(0);
if (nodeCntr < contents.length / 4 && nodeCntr > MIN_CAPACITY)
resizeArray(nodeCntr / 2);
}
return result;
}
// private methods
// ---------------
/* For the purpose of resizing contents[] when either it becomes
** full or too close to empty.
*/
private void resizeArray(int newSize) {
T[] newArray = (T[])(new Object(newSize));
for (int i=0; i != nodeCntr; i++) {
newArray[i] = contents[i]);
}
contents = newArray;
}
/* Returns true iff the first argument is greater than the
** second, according to the resident comparator.
*/
private boolean greaterThan(T a, T b)
{ return c.compare(a, b) > 0; }
// tree navigation operations
// --------------------------
private int rootLoc() { return 0; }
private int parentLoc(int v) { return (v-1) / 2; }
private int leftChildLoc(int v) { return 2*v + 1; }
private int rightChildLoc(int v) { return 2*v + 2; }
// tree observer operations
// ------------------------
private boolean hasLeftChild(int v)
{ return leftChildLoc(v) < nodeCntr; }
private boolean hasRightChild(int v)
{ return rightChildLoc(v) < nodeCntr; }
private boolean isLeaf(int v) { return !hasLeftChild(v); }
/* Swaps the item stored in node #k upwards towards the root
** until either it reaches the root or is not greater than the
** item in its parent node, whichever comes first.
** (This version is intended to be recursive.)
*/
private siftUp(int k) {
// code omitted
}
/* Swaps the item stored in node #k upwards towards the root
** until either it reaches the root or is not greater than the
** item in its parent node, whichever comes first.
** (This version is intended to use a loop.)
*/
private siftUpIterative(int k) {
// code omitted
}
/* Swaps the item stored in node #k downwards towards its
** descendant leaves until either it reaches a leaf or is
** at least as large as the item(s) in its child(ren),
** whichever comes first.
** (This version is intended to be recursive.)
*/
private siftDown(int k) {
// code omitted
}
/* Swaps the item stored in node #k downwards towards its
** descendant leaves until either it reaches a leaf or is
** at least as large as the item(s) in its child(ren),
** whichever comes first.
** (This version is intended to use a loop.)
*/
private siftDownIterative(int k) {
// code omitted
|