package dataStructures;
public class MinMaxHeap implements MaxPriorityQueue, MinPriorityQueue {
// data members
Comparable[] heap; // array for complete binary tree
int size; // number of elements in heap
//add any helper method when necessary
public MinMaxHeap(int initialCapacity) {
if (initialCapacity < 1)
throw new IllegalArgumentException
("initialCapacity must be >= 1");
heap = new Comparable[initialCapacity + 1];
size = 0;
}
public MinMaxHeap() {
this(10);
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public Comparable getMax() {
//your code here
}
public Comparable getMin() {
// your code here
}
public void put(Comparable theObject) {
// your code here
}
public Comparable removeMax() {
// your code here
}
public Comparable removeMin() {
//your code here
}
public void initialize(Comparable[] theHeap, int theSize) {
heap = theHeap;
size = theSize;
for (int root = size / 2; root >= 1; root--) {
if (isMinLevel(root)) {
processMinLevel(root);
} else { //max level
processMaxLevel(root);
}
}
}
//method used by initialize()
private void processMinLevel(int root) {
int child;
while ((child = root * 2) <= size) {//root has at least one child
int minchild = -1;
int mingrandchild = -1;
int grandchild = 2 * child;
minchild = child;
//find smallest grandchild if there is one
if (grandchild <= size) mingrandchild = grandchild++;
while (grandchild <= size && grandchild <= child * 2 + 3) {
if (heap[grandchild].compareTo(heap[mingrandchild]) < 0)
mingrandchild = grandchild;
grandchild++;
}
//find smallest child
if (child < size &&
heap[child].compareTo(heap[child + 1]) > 0) minchild++;
//check if minchild is smaller than the grandchildren
if (mingrandchild == -1 ||
heap[minchild].compareTo(heap[mingrandchild]) < 0) {
if (heap[minchild].compareTo(heap[root]) < 0)
swap(minchild, root);
break;
}
if (heap[mingrandchild].compareTo(heap[root]) < 0) {
swap(root, mingrandchild);
//now the grandchilds parent might be smaller than the grandchild
int parent = mingrandchild / 2;
if (heap[parent].compareTo(heap[mingrandchild]) < 0) {
swap(parent, mingrandchild);
}
root = mingrandchild; //need to continue with the grandchild
} else break;
}
}
//method used by initialize()
private void processMaxLevel(int root) {
int child;
while ((child = root * 2) <= size) {
int maxchild = -1;
int maxgrandchild = -1;
int grandchild = 2 * child;
maxchild = child;
if (grandchild <= size) maxgrandchild = grandchild++;
while (grandchild <= size && grandchild <= child * 2 + 3) {
if (heap[grandchild].compareTo(heap[maxgrandchild]) > 0)
maxgrandchild = grandchild;
grandchild++;
}
if (child < size &&
heap[child].compareTo(heap[child + 1]) < 0) maxchild++;
if (maxgrandchild == -1 ||
heap[maxchild].compareTo(heap[maxgrandchild]) > 0) {
if (heap[maxchild].compareTo(heap[root]) > 0)
swap(maxchild, root);
break;
}
if (heap[maxgrandchild].compareTo(heap[root]) > 0) {
swap(root, maxgrandchild);
int parent = maxgrandchild / 2;
if (heap[parent].compareTo(heap[maxgrandchild]) > 0) {
swap(parent, maxgrandchild);
}
root = maxgrandchild;
} else break;
}
}
//swaps the elements with the given indices in the heap
private void swap(int m, int n) {
Comparable temp = heap[n];
heap[n] = heap[m];
heap[m] = temp;
}
//returns true if the node is in the min level, false otherwise
private boolean isMinLevel(int node) {
return (int) (Math.log(node) / Math.log(2)) % 2 == 0;
}
public String toString() {
StringBuffer s = new StringBuffer();
s.append("The " + size + " elements are [");
if (size > 0) {// nonempty heap
// do first element
s.append(heap[1]);
// do remaining elements
for (int i = 2; i <= size; i++)
s.append(", " + heap[i]);
}
s.append("]");
return new String(s);
}
public int lb(int n) {
int v = 0;
while (n > 0) {
n = n / 2;
v++;
}
return v;
}
public void print() { //print the heap as a tree
int depth = lb(size);
int space = 2 ^ depth;
for (int i = 0; i < depth; i++) {
space = (1 << (depth - i)) / 2;
String blank = "";
String out = "";
for (int j = 0; j < space; j++) {
out += "\t";
}
for (int j = 0; j < space; j++) {
blank += "\t\t";
}
for (int j = 0; j < 1 << (i); j++) {
int index = j + (1 << (i)) - 1;
if (index >= size) {
break;
}
if (heap[index + 1] != null) {
out += heap[index + 1].toString() + blank;
} else {
out += "n" + blank;
}
}
System.out.println(out);
}
}
public static void main(String[] args) {
MinMaxHeap h = new MinMaxHeap(1);
h.put(new Integer(-72));
h.put(new Integer(56));
h.put(new Integer(39));
h.put(new Integer(-29));
h.put(new Integer(93));
h.put(new Integer(7));
h.put(new Integer(-19));
h.put(new Integer(26));
h.put(new Integer(2));
h.put(new Integer(-1));
//h.print();
System.out.println("Elements in array order are");
System.out.println(h);
System.out.println();
// test remove max
System.out.println("The min element is " + h.getMin());
System.out.println("The max element is " + h.getMax());
for (int i = 0; i < 2; i++) {
System.out.println("Deleted min element " + h.removeMin());
//h.print();
System.out.println();
}
System.out.println(h);
for (int i = 0; i < 2; i++) {
System.out.println("Deleted max element " + h.removeMax());
//h.print();
System.out.println();
}
System.out.println(h);
// test initialize
Comparable[] z = new Comparable[30];
for (int i = 1; i < 30; i++)
z[i] = new Integer(i);
MinMaxHeap mh = new MinMaxHeap(30);
mh.initialize(z, 29);
System.out.println("Our Min-Max Heap is");
//mh.print();
System.out.println(mh);
}
}
|
