assignment 5/Assignment 5 Solution.pdf
Assignment 5
The goal of this collection of assignment is to help you review (i)
Priority Queue.

Q1 In lecture 8, we introduced the ADT for priority queues. What does each
remove_min() call return within the following sequence of priority queue ADT
methods: add(1,a), add(3,b), add(2,c), add(5,e), remove_min( ), add(4,j),
add(9,k), remove min(), remove min()? Please provide the returned keys only in
your answers.
A public static void main(String[] args)
{
ArrayList s = new ArrayList<>();
PriorityQueue queue = new PriorityQueue();
queue.add(new MyClass(1, "a"));
queue.add(new MyClass(3, "b"));
queue.add(new MyClass(2, "c"));
queue.add(new MyClass(5, "e"));
s.add(queue.element().value);
queue.remove();
queue.add(new MyClass(4, "j"));
queue.add(new MyClass(9, "k"));
s.add(queue.element().value);
queue.remove();
s.add(queue.element().value);
queue.remove();
System.out.println("Priority Queue:" + queue)
System.out.println("Removes Items:" +s);
}
class MyCLass implements Comparable
{
int priority;
String value;
Public MyClass(int p, String v)
{
this.priority = p;
this.value = v;
}
@Override
public int compareTo(MyClass other)
{
return Integer.compare(priority, other.priority);
}
public String toString()
{
return priority + ", " + value;
}
}
Q2 Let H be a heap storing 15 entries using the array-based representation of a
complete binary tree. What is the sequence of indices of the array that are visited
in a preorder traversal of H? What about an inorder traversal of H? What about a
postorder traversal of H? Let us assume array indices start from 1.
A Preorder : 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
Inorder : 8 4 9 2 10 ...