[JAVA] Implement a Java class MaxHeap as specified below to support the operatio

Question

[JAVA]

Implement a Java class MaxHeap as specified below to support the operations of max heaps, heapsort, and priority queues. Use the exact class and method names given and use the default package. Note that when adopting the pseudocode from the book you need to make adjustments on array indices because Java arrays are 0-based public class MaxHeap // reference to the arra)y public int[] a; // heapSize may be different from a.length public int heapSize; // construct a MaxHeap object // reference (do not copy) the user supplied array public MaxHeap(int[] a) public void heapify(int i) public void buildHeap() // heapsort on a public void sort() // priority queue operations public int maximum() public int extractMax() public void increaseKey (int i, int key) public void insert(int key)

Explanation / Answer

public class HeapExample {

private int[] a;
private int size;
private int maxsize;

private static final int FRONT = 1;

public HeapExample(int maxsize) {
this.maxsize = maxsize;
this.size = 0;
a = new int[this.maxsize + 1];
a[0] = Integer.MAX_VALUE;
}

private int parent(int pos) {
return pos / 2;
}

private int leftChild(int pos) {
return (2 * pos);
}

private int rightChild(int pos) {
return (2 * pos) + 1;
}

private boolean isLeaf(int pos) {
if (pos >= (size / 2) && pos <= size) {
return true;
}
return false;
}

private void swap(int fpos, int spos) {
int tmp;
tmp = a[fpos];
a[fpos] = a[spos];
a[spos] = tmp;
}

private void maxHeapify(int pos) {
if (!isLeaf(pos)) {
if (a[pos] < a[leftChild(pos)] || a[pos] < a[rightChild(pos)]) {
if (a[leftChild(pos)] > a[rightChild(pos)]) {
swap(pos, leftChild(pos));
maxHeapify(leftChild(pos));
} else {
swap(pos, rightChild(pos));
maxHeapify(rightChild(pos));
}
}
}
}

public void insert(int element) {
a[++size] = element;
int current = size;

while (a[current] > a[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}

public void print() {
for (int i = 1; i <= size / 2; i++) {
System.out.print(
" PARENT : " + a[i] + " LEFT CHILD : " + a[2 * i] + " RIGHT CHILD :" + a[2 * i + 1]);
System.out.println();
}
}

public void maxHeap() {
for (int pos = (size / 2); pos >= 1; pos--) {
maxHeapify(pos);
}
}

public int remove() {
int popped = a[FRONT];
a[FRONT] = a[size--];
maxHeapify(FRONT);
return popped;
}

public static void main(String... arg) {
System.out.println("max heap is ");
HeapExample max= new HeapExample(15);
max.insert(5);
max.insert(3);
max.insert(17);
max.insert(10);
max.insert(84);
max.insert(19);
max.insert(6);
max.insert(22);
max.insert(9);
max.maxHeap();

max.print();
System.out.println("The max val is " + max.remove());
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.