Question

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap, you need to assign a priority (key) to each item that will determine where it is inserted in the heap

a) Show how to assign priorities to items to implement a first-in, first-out queue with a heap.

b) Show how to assign priorities to items to implement a first-in, last-out stack with a heap.

Answer 1

Solution to part (a) with java code :

The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap:

• The root of the heap is always in array[1].
• Its left child is in array[2].
• Its right child is in array[3].
• In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1].
• If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1).

Note that the heap's "shape" property guarantees that there are never any "holes" in the array.

The operations that create an empty heap and return the size of the heap are quite straightforward; below we discuss the insert and removeMax operations.

Insert:

When a new value is inserted into a priority queue, we need to:

• Add the value so that the heap still has the order and shape properties, and
• Do it efficiently!

The way to achieve these goals is as follows:

1. Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1).
2. Step 1 above ensures that the heap still has the shape property; however, it may not have the orderproperty. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-and-swap procedure up the tree until we find that the order property holds, or we get to the root.

RemoveMax:

Because heaps have the order property, the largest value is always at the root. Therefore, the removeMaxoperation will always remove and return the root value; the question then is how to replace the root node so that the heap still has the order and shape properties.

The answer is to use the following algorithm:

1. Replace the value in the root with the value at the end of the array (which corresponds to the heap's rightmost leaf at depth d). Remove that leaf from the tree.
2. Now work your way down the tree, swapping values to restore the order property: each time, if the value in the current node is less than one of its children, then swap its value with the larger child (that ensures that the new root value is larger than both of its children).

Java code:

package Question1_1;

public class PriorityQueueUsingHeap<T extends Comparable<T>> {
T[] arr;
int N;

public static void main(String[] args) {
PriorityQueueUsingHeap<Integer> pq = new PriorityQueueUsingHeap<Integer>();
pq.insert(3);
System.out.println(pq.toString());
pq.insert(5);
System.out.println(pq.toString());
pq.insert(2);
System.out.println(pq.toString());
pq.insert(-1);
System.out.println(pq.toString());
pq.insert(9);
System.out.println(pq.toString());
pq.insert(4);
System.out.println(pq.toString());

pq.delMax();
System.out.println(pq.toString());
pq.delMax();
System.out.println(pq.toString());
pq.delMax();
System.out.println(pq.toString());
pq.delMax();
System.out.println(pq.toString());
pq.delMax();
System.out.println(pq.toString());
}

public PriorityQueueUsingHeap(){
arr = (T[]) new Comparable[2];
N = 0;
}

public void insert(T t){
if (N == arr.length - 1) resize(2*N + 1);
arr[++N] = t;
swim(N);
}

public T delMax(){
if (isEmpty()) return null;
T t= arr[1];
exch(1,N--);
arr[N+1] = null;
sink(1);

//resize this array
if (N == (arr.length -1)/4) resize((arr.length-1) / 2 + 1);
return t;
}
//helper methods
public String toString(){
StringBuffer sb = new StringBuffer();
for(int i = 1; i <= N; i ++)
sb.append(arr[i].toString()+" ");
return sb.toString();
}

private boolean isEmpty(){
return N == 0;
}
private void resize(int capacity){
T[] copy = (T[]) new Comparable[capacity];
for(int i = 1; i <= N; i ++ )
copy[i] = arr[i];
arr = copy;
}

private void swim(int k){
while(k > 1 && less(k/2, k)){
exch(k/2,k);
k = k/2;
}
}

private void sink(int k){
while (2*k < N){
int j = 2 * k;
if(j < N && less(j, j +1)) j = j + 1;
if(less(j, k)) break;
exch(k,j);
k = j;
}
}

private boolean less(int i, int j){
if (arr[i].compareTo(arr[j]) < 0)
return true;
return false;
}

private void exch(int i, int j){
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}