how to implement an insert method for the heap program below? import java.util.A

Question

how to implement an insert method for the heap program below?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxHeap<X extends Comparable<X>> {
List<X> list = new ArrayList<X>();

public String toString() { return list.toString(); }

int size() { return list.size(); }

private int left(int k) {
return 2 * k;
}
private int right(int k) {
return 2 * k + 1;
}
private int parent(int k) {
return k / 2;
}
private void swap(int i, int j) {
i--; j--;
X tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
}
private X getData(int k) {
return list.get(k-1);
}
// how to insert x into the heap
void insert(X x) {
// TODO
}
// replace the top of the heap with x
void replace(X x) {
// TODO
}

public static void main(String[] args) {
Integer[] data = { 4, 1, 3, 11, 6, 5, 13, 16, 8, 9 };

MaxHeap<Integer> h = heapify(data);

System.out.println("Input data array: " + Arrays.toString(data) + " ");

System.out.println("Result of heapify: " + h + " ");

int size = h.size();

System.out.println("top heap after removing the top ");
for(int i=0; i<size; i++) {
System.out.println(h.pop() + " " + h);
}
}

// methods called by test cases
boolean report(String s) {
System.err.println(s);
return false;
}
boolean wellFormed() {
for (int i = 0; i < list.size() / 2; i++) {
X parent = list.get(i);
X left = list.get(i*2 + 1);
if (parent.compareTo(left) < 0)
return report(parent + " has " + left + " as left child");
int k = i*2 + 2;
if (k < list.size()) {
X right = list.get(k);
if (parent.compareTo(right) < 0)
return report(parent + " has " + right + " as right child");
}
}
return true;
}
}

Explanation / Answer

Answer

void insert(X x){

Heap[++size] = x;

X current = size;

while(Heap[current]>Heap[parent(current)]){

swap(current,parent(current));

current = parent(current);

}

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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