Implementing a Priority Queue 1. Background Our goal will be to implement a Priority Queue. Specifically, a min heap. Although heaps may seem pretty straightforward, they can be used in abstract ways to solve difficult problems. Additionally, they are of utmost importance when dealing with greedy algorithms, like Dijktras shortest path algorithm that are in the cornerstone of modern technology (think Google Maps). Today we are going to solve a more straightforward question dealing with matrix and the p-smallest values within it. 2. Requirements For this assignment, you will implement the provided priority queue interface (see PriorityQueue.java).

This interface file does not only define which methods you must implement, but gives you documentation that describes how they should work. Creating the ADT will involve creating x methods: public interface PriorityQueue { boolean isEmpty(); int size(); Key min(); // resize the underlying array to have the given capacity void resize(int capacity); void insert(Key x); Key delMin(); void swim(int k); void sink(int k); boolean greater(int i, int j); void exchange(int i, int j); } After implementing your priority queue, you will use it to solve a single question several times. You are given an 100x100 matrix. The rows and columns are given in non- decreasing order. Lets call the row index r and the column index c. This means that matrix[r][c]

1. Your job is to find the 30th 920th and 2430th value, which we will call the P values. a. Note, 7 is 5th smallest, 8 is 6th smallest, 9 is 7th smallest, etc. 2. You must use your priority queue to solve this question. Additionally, you must adhere to the following contains: a. Time complexity will be at most O(P + P(log(P)) b. Space complexity will be O(P)

1 After implementing your priority queue, you will use it to solve a single question several times. You are given an 100x100 matrix. The rows and columns are given in non- decreasing order. Let's call the row index"" and the column index"c". This means that matrix[r][c]