Instructions
Requirements and Specifications
Source Code
HEAP
//
//
// The code for the class Heap.
//
// public methods:
// insert (HeapElem newElement): insert a new element (with an integer key and a double data fields) to the heap
// extractMax (): remove and return the data field of the heap element with maximum key
// isEmpty(): return true if the heap is empty, false otherwise.
// getSize(): return the number of elements in the heap
// getMax(): return the data field of the heap element with the maximum key
// preOrder(): print the heap elements (their key and data fields) in pre-order
public class Heap implements PriorityQueueADT {
private HeapElem[] heap; // the tree represented with an array
private int size, maxSize;
// the constructor for an originally empty heap
public Heap(int newSize) {
maxSize = newSize;
heap = new HeapElem[maxSize];
size = 0;
}
// the constructor when the heap is initiated with an array a. The array is heapified by calling buildHeap.
public Heap(HeapElem[] a) {
heap = a;
size = a.length;
buildHeap();
}
// from bottom to top, call reheapDown (bubble down).
private void buildHeap() {
// update this to call reheapDown a smaller number of times.
if (size <= 1) {
return;
}
int lastToCheck = (size - 2)/2;
for (int i = lastToCheck - 1; i >= 0; i--)
reheapDown(i);
}
// swap is called from reheapDown and reheapUp
private void swap(int i, int j) {
HeapElem temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
// bubble up the element at position index; called from insert
private void reheapUp(int index) {
int parent = (index + 1) / 2 - 1;
if (index > 0 && heap[parent].key < heap[index].key) {
swap(parent, index);
reheapUp(parent);
}
}
// bubble down the element at position index; called from insert
private void reheapDown(int top) {
int maxChild;
int left = 2 * top + 1;
int right = 2 * top + 2;
if (left < size) {
if (right >= size || heap[left].key > heap[right].key)
maxChild = left;
else
maxChild = right;
if (heap[top].key < heap[maxChild].key) {
swap(top, maxChild);
reheapDown(maxChild);
}
}
}
// insert; place the newKey in the last position, reheapUp, and update size
public void insert(HeapElem newElement) {
if (size < maxSize) {
heap[size] = newElement;
reheapUp(size);
size++;
}
}
// insert; place the newKey in the last position, reheapUp, and update size
public void insert(int key, double data) {
HeapElem newElement = new HeapElem(key, data);
insert(newElement);
}
// remove and return the data field of the heap element with the maximum key
public double extractMax() {
HeapElem res = null;
if (size > 0) {
res = heap[0];
heap[0] = heap[--size];
reheapDown(0);
}
return res.data;
}
// return true if the heap is empty, false otherwise.
public boolean isEmpty() {
return size == 0;
}
// return the number of elements in the heap
public int getSize() {
// implement this.
return size;
}
// return the data field of the heap element with the maximum key
public double getMax() {
// implement this.
return heap[0].data;
}
// print the heap elements (their key and data fields) in pre-order
public void preOrder() {
if (size == 0) {
return;
}
preorderStep(0);
}
private void preorderStep(int i) {
heap[i].print();
if (2*i + 1 < size) {
preorderStep(2*i + 1);
if (2*i + 2 < size) {
preorderStep(2*i + 2);
}
}
}
}
PRIORITY QUEUE ADT
//
// This code declares the interface PriorityQueueADT including signatures and the public methods.
public interface PriorityQueueADT {
public void insert ( int key, double data );
public double extractMax() ;
public double getMax() ;
public boolean isEmpty() ;
public int getSize() ;
}