Implement Priority Queues in Java Assignment Solution

Instructions

Objective

Write a java homework program to implement priority queues.

Requirements and Specifications

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 Diktra's 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 13Empty () ; int size (); Key min (); // resize the underlying array to have the given capacity vold resize (ant capacity); void insert (Key x) ; Key delMin (); void swim(int k); void sink (int k); boolean greater (int i, int j); vold exchange ant 1, 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. Let's call the row index "" and the column index "C

This means that matrix[r][c] <= matrix[r + 1](c] AND matrix|rilcl <= matrixirilc + 11.

0

5

8

+13

1

7

10

20

9

12

22

11

14

24

• Your job is to find the 30th 920th and 2430* value, which we will call the P values.Note, 7 is 5th smallest, 8 is 6th smallest, 9 is 7th smallest, etc.
• You must use your priority queue to solve this question. Additionally, you must adhere to the following contains:

Time complexity will be at most O(P + P(log(P))

Space complexity will be O(P)

Source Code

import java.io.File; import java.io.IOException; import java.util.*; /** * PriorityQueue class implemented via the binary heap. (max heap) */ public class PriorityQueueInt implements PriorityQueue { private static final int INITSIZE = 100; private int currentSize; // Number of elements in heap private int[] array; // The heap array /** * Construct an empty PriorityQueue. */ public PriorityQueueInt() { currentSize = 0; array = new int[INITSIZE + 1]; } /** * Indicates whether the heap is empty. * * @return true if the list is empty, false otherwise. **/ @Override public boolean isEmpty() { return currentSize == 0; } /** * Returns the number of items in this PriorityQueueInt. * * @return the number of items in this PriorityQueueInt. */ @Override public int size() { return currentSize; } /** * Returns the smallest int in the priority queue. * * @return the smallest item. * @throws NoSuchElementException if empty. */ @Override public Integer min() { if (isEmpty()) throw new NoSuchElementException(); return array[1]; } /** * Extends array ot the given size. * * @param capacity new array capacity */ @Override public void resize(int capacity) { int[] newArray; newArray = new int[capacity]; System.arraycopy(array, 0, newArray, 0, array.length); array = newArray; } /** * Inserts an int to this PriorityQueueInt. * * @param x integer. */ @Override public void insert(Integer x) { if (currentSize + 1 == array.length) resize(2 * array.length); int hole = ++currentSize; array[hole] = x; swim(hole); } /** * Removes the smallest int from the priority queue. * * @return the smallest int. * @throws NoSuchElementException if empty. */ public Integer delMin() { int minItem = min(); array[1] = array[currentSize--]; sink(1); return minItem; } /** * Percolates down in the heap. * * @param k the index at which the percolate begins. */ @Override public void sink(int k) { int child; int tmp = array[k]; for (; k * 2 <= currentSize; k = child) { child = k * 2; if (child != currentSize && greater(child, child + 1)) child++; if (greater(k, child)) exchange(child, k); else break; } array[k] = tmp; } /** * Percolate up in the heap. * * @param k the index at which the percolate begins. */ @Override public void swim(int k) { int parent; int tmp = array[k]; for (; k / 2 >= 1; k = parent) { parent = k / 2; if (greater(parent, k)) exchange(k, parent); else break; } array[k] = tmp; } /** * Indicates, whether element at first index is greater than element at second index * @param i first index * @param j second index * @return true, element at first index is greater than element at second index */ @Override public boolean greater(int i, int j) { return array[i] > array[j]; } /** * Exchanges elements at first index with element at second index * @param i first index * @param j second index */ @Override public void exchange(int i, int j) { int sw = array[i]; array[i] = array[j]; array[j] = sw; } public static void main(String[] args) throws IOException { PriorityQueue pq = new PriorityQueueInt(); try(Scanner scanner = new Scanner(new File("testcase-1.txt"))) { String line = scanner.nextLine(); line = line.replaceAll("[\\[,\\]]", " ").trim(); String[] parts = line.split("\\s+"); for (String s : parts) { pq.insert(Integer.parseInt(s)); } Set toFind = new HashSet<>(); toFind.add(30); toFind.add(920); toFind.add(2430); int counter = 1; while(!pq.isEmpty()) { int min = pq.delMin(); if (toFind.contains(counter)) { System.out.println(counter + "th value is " + min); } counter++; } } } }