Here we want to be able to directly locate where a value is in the heap array without having to search for it which would be too inefficient. The highest priority value is easy to find as it is at the top of the heap, but other values could be anywhere. To do this we use an extra array called hPos[] which records the index of where each value is stored in heap array a[]. Modify your heap code to do the following:

• Add the extra array called hPos[] to the heap, it should be the same size as the heap array a[]. Modify the Heap constructors to do this.

• modify code in insert() and siftUp() to update this array in an appropriate way. Basically hPos[v] stores the position of where vertex v is on the heap. So when you move a vertex from a[k/2] to a[k], you should update hPos[].

• update hPos[] for siftDown() and remove()

// Heap.java // Skeleton code

class Heap { private static int[] a; int N; static int maxH = 100;

// two constructors Heap() { N = 0; a = new int[maxH + 1]; }

Heap(int size) { N = 0; a = new int[size + 1]; }

void siftUp(int k) { int v = a[k]; a[0] = Integer.MAX_VALUE;

// complete yourself from pseudocode in notes while (v > a[k / 2]) { a[k] = a[k / 2]; k = k / 2; } a[k] = v;

}

void siftDown(int k) { int v, j; v = a[k]; // complete yourself while (2 * k = a[j]) { break; } a[k] = a[j]; k = j; } a[k] = v;

}

void insert(int x) { a[++N] = x; siftUp(N); }

int remove() { a[0] = a[1]; // store highest priority value in a[0] a[1] = a[N--]; // and replace it with value from end of the heap siftDown(1); // and then sift this value down return a[0]; }

void display() { System.out.println(" The tree structure of the heaps is:"); System.out.println(a[1]); for (int i = 1; i

boolean isEmpty() { // return N == 0; if(N == 0) { return true; } return false; } public static void main(String args[]) {

Heap h = new Heap(); int r; double x;

// insert random numbers between 0 and 99 into heap for (int i = 1; i

while (!h.isEmpty()) { r = h.remove(); System.out.println("Removed: " + r); // h.display(); }

}

} // end of Heap class

hPos is another array with the same size of the original array that stores the heaps values.

lets say you are looking for value 1 we can see its in the index position at 6, this the heap array. But what I want to do in is add an array with the same size and name it hPos. hPos array will store 6 in the index of 1.

7 is in index 2 in the original array. but we the value 7 in index 2 in the hPos array.

another example 8 is not in the heap. so in hPos in index 8 we put 0.

Please look at the image provided. This is just a fast way to find things in the heap