/**
* Deg2Heap.java<BR>
* Definitions for degree-2 heap implementation of an Heap ADT.
* <P>
* A binary heap/array implementation of the Heap ADT.<BR>
* This implementation uses an array (size determined by a parameter
* to the constructor) to make a binary min-heap of int values,
* in order to implement the ADT Heap interface. The "insert" and
* "removeMin" methods take O(log n) time, and the "Min", "isEmpty"
* and "size" methods take O(1) time.
* <P>
* Last Update: Oct. 24, 2005
*/
public class Deg2Heap implements Heap {
///////////////////////////////////////////////////////////////
// Global variables and Constructor
///////////////////////////////////////////////////////////////
/**
* pointer to the array of int values.
* Heap values are stored at indices 1 and onwards.
*/
private int[] array;
/**
* physical size of the array.
*/
private int arraySize;
/**
* number of elements actually stored in the array.
*/
private int inUse; // index of last element as well.
/**
* Constructor.
* @param size The minimum number of elements this priority queue
* will have to hold.
*/
public Deg2Heap(int size) {
size++; // index 0 is not used.
array = new int[size];
arraySize = size;
inUse = 0;
} // Deg2Heap
///////////////////////////////////////////////////////////////
// Local functions
///////////////////////////////////////////////////////////////
/**
* Return leftchild position
*
* @param pos index of the parent.
* @return index of left child of parent.
*/
private int leftchild(int pos) {
return 2*pos;
}
/**
* Return rightchild position
*
* @param pos index of the parent.
* @return index of right child of parent.
*/
private int rightchild(int pos) {
return 2*pos + 1;
}
/**
* Return parent position
*
* @param pos index of a child.
* @return index of the parent of the child.
*/
private int parent(int pos) {
return pos/2;
}
/**
* TRUE if pos is a leaf
*
* @param pos index of node being tested.
* @return boolean value indicating if node is a leaf.
*/
private boolean isLeaf(int pos) {
return ((pos > inUse/2) && (pos <= inUse));
}
///////////////////////////////////////////////////////////////
// Class methods
///////////////////////////////////////////////////////////////
/**
* Insert a new value into the priority queue.
* @param key The key value to insert.
* @return The inserted key value.
*/
public int insert(int key) {
if (inUse >= arraySize)
System.err.println("Inserting while heap is full");
if (inUse < arraySize) {
inUse++;
int curr = inUse;
array[curr] = key; // Start at end of heap
// Now sift up until the key of curr's parent <= key of curr
while ( (curr > 1) &&
(array[curr] < array[parent(curr)]) ) {
array[curr] = array[parent(curr)];
array[parent(curr)] = key; // swap key into parent's spot
curr = parent(curr); // curr is now the key's location.
} // while
} // if
return key;
} // insert
/**
* Get the minimum value in the priority queue.
* @return The minimum value.
*/
public int min() {
if (inUse == 0)
System.err.println("oops...");
return array[0];
} // min
/**
* Remove the largest key value from the priority queue.
* @return The removed minimum value.
*/
public int removeMin() {
int minChild;
int removeKey = array[1]; // root key value
if (inUse < 1)
System.err.println("Removing from empty heap");
else
if (inUse > 1) {
int curr = 1;
array[curr] = array[inUse]; // Swap minimum with last value
inUse--; // one less value.
// Put new heap root val in correct place
while (!isLeaf(curr)) {
minChild = leftchild(curr);
if ( (minChild < inUse) && // if there is a right child...
(array[leftchild(curr)] > array[rightchild(curr)]) )
minChild = rightchild(curr);
// minChild is now index of child with smaller value
if (array[curr] <= array[minChild])
return removeKey; // Done and break out of while loop.
int temp = array[curr]; // swap keys
array[curr] = array[minChild];
array[minChild] = temp;
curr = minChild; // Move down to child
} // while
} // if
return removeKey;
} // removeMin
/**
* Is the priority queue empty?
* @return true if and only if the priority queue is empty.
*/
public boolean isEmpty() {
return (inUse == 0);
} // isEmpty
/**
* Size of the priority queue.
* @return Number of key values in priority queueu.
*/
public int size() {
return inUse;
} // size
/**
* Is the priority queue in Min-Heap order? Do not modify the
* implementation of this method.
*
* @return true if and only if the priority queue is in heap order.
*/
public boolean testHeap() {
boolean heapOrder = true;
for (int i=2; i < inUse+1; i++) {
if (array[i] < array[parent(i)]) {
heapOrder = false;
// if a problem with order, some diagnostics are printed.
System.out.println();
System.out.println("Testing heap order for size = " + inUse);
System.out.print("i: " + i + ": parent(i) = " + parent(i));
System.out.print(": heap[i] = " + array[i]);
System.out.println(": heap[parent(i)] = " + array[parent(i)]);
} // ir
} // for
if (!heapOrder)
System.out.println("Heap is NOT in Min-heap order as expected");
return heapOrder;
} // testHeap
} Powered by
GeSHi Syntax Highlighting software.
Author of all (other) material unless otherwise specified:
Loren Segal. Copyright 2005.