Question

Given the following program with fill in the blanks, implement the PQ class which is priority Queue MAX heap; the higher the number, the higher the prority of that number. None of the public methods has been implemented. You will need to write other methods to help implement some of the methods. For example you will need to implement bubbleUp to help with the insert method.

Methods to implement:

insert -> insert one element into the PQ and maintain heap shape/ order

remove-> remove the highest priority and maintain heap shape/order

poll -> gets the highest priority without removing

heapify -> build a priority queue from a given list of numbers

toSortedList-> removes all elements from the PQ into a list such that is is sorted from highest to lowest priority.

_________________________________________________________________________________________________________

public class PQimplement {

public static void main(String args[]){

List list = randomList(20);

System.out.println("Unsorted Input List: " + list.toString());

PQ priorityQueue = new PQ(list);

List sortedList = priorityQueue.toSortedList();

System.out.println("Sorted List Descending order: " + list.toString());

}

private static List randomList(int size){

final Random rng = new Random();

List list = new ArrayList<>(size);

for(int i = 0; i< size; i++){

list.add(rng.nextInt()%10);

}

return list;

}

}

public class PQ {
	int data[];
	int size;
	int capacity;
	PQ(int capacity){
	this.capacity = capacity;
	size = 0;
	data = new int[capacity];
	}
	PQ(){
	capacity = 1000;
	size = 0;
	data = new int[capacity];
	}
	PQ(List data){
	capacity = data.size() > 1000 ? data.size() : 1000;
	size = data.size();
	heapify(data);
	}
	public void insert(int data){
	//Insert the new data into the PQ, ensure the heap maintains heap order/shape
	//fill in
	}
	public void remove(){
	//Removes the root or the node with the highest priority
	//fill in
	}
	public int poll(){
	//Returns the node with the highest priority. This method should NOT remove that node
	//fill in
	return -1;
	}
	private void heapify(List data){
	//implement the heapify method that will build a PQ given a list of data
	}
	public List toSortedList(){
	//this method will return a list of all the integers in the priority queue in sorted order (Max Heap)
	//this method will remove all the data from the pq
	}
	}

Answer 1

// PQ.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PQ {
  
   int data[];
   int size;
   int capacity;
  
   PQ(int capacity){
       this.capacity = capacity;
       size = 0;
       data = new int[capacity];
   }
  
   PQ(){
       capacity = 1000;
       size = 0;
       data = new int[capacity];
   }
  
   PQ(List<Integer> data){
       capacity = data.size() > 1000 ? data.size() : 1000;
       size = data.size();
       heapify(data);
   }
  
   public void insert(int data){
       //Insert the new data into the PQ, ensure the heap maintains heap order/shape
       if(size == capacity) // array is full
       {
           // expand the array by twice its capacity
           this.data = Arrays.copyOf(this.data, capacity*2);
           capacity = 2*capacity;
       }
      
       // insert the data at the end of the array
       this.data[size] = data;
       bubbleUp(size); // move up the data at the correct position
       size++; // increment the size
      
   }
  
   // private helper method to move the element up to occupy its correct position
   private void bubbleUp(int index)
   {
       int item = data[index]; // get the item at index
       int parent = (index-1)/2; // get the index of its parent
      
       // loop to move the element up so that it occupies its correct position to maintain a MaxHeap
       while(index > 0 && data[parent] < item)
       {
           // set data at index to data at parent
           data[index] = data[parent];
           index = parent; // make index as parent index
           parent = (index-1)/2; // get the index of parent
       }
      
       data[index] = item; // set item at index
   }
  
   // method to remove the maximum priority element
   public void remove(){
       if(size > 0) // array is not empty
       {
           // replace the data at 0 with the last element
           data[0] = data[--size];
           bubbleDown(0); // method to move the element down to its correct position
       }
   }
  
   // helper method to restore the MaxHeap
   private void bubbleDown(int index)
   {
       int left = 2*index+1; // get the index of left child
       int right = 2*index+2; // get the index of right child
      
       int max = index;
      
       // get the index of element with maximum priority
       if((left < size) && (data[left] > data[max]))
           max = left;
       if((right < size) && (data[right] > data[max]))
           max = right;
       // if index of maximum priority is not index, swap the index and max elements and call the method with max as its index
       if(max != index)
       {
           int temp = data[max];
           data[max] = data[index];
           data[index] = temp;
           bubbleDown(max);
       }
   }

   public int poll(){
       //Returns the node with the highest priority. This method should NOT remove that node
       if(size > 0)
           return data[0];
       return -1;
   }
  
   private void heapify(List<Integer> data){
       //implement the heapify method that will build a PQ given a list of data
      
       // create data of capacity
       this.data = new int[capacity];
       size = 0; // set size to 0
      
       // loop to insert the elements from data list
       for(int i=0;i<data.size();i++)
       {
           insert(data.get(i));
       }
   }
  
   public List<Integer> toSortedList(){
       //this method will return a list of all the integers in the priority queue in sorted order (Max Heap)
       //this method will remove all the data from the pq
       List<Integer> sorted = new ArrayList<Integer>();
      
       // loop that continues till there are elements in the list
       while(size > 0)
       {
           sorted.add(poll()); //add the current top priority element to the list
           remove(); // remove the current top priority element
       }
      
       return sorted;
   }
}

//end of PQ.java

// PQAssignment.java

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class PQAssignment {

   public static void main(String[] args) {

       List<Integer> list = randomList(20);
       System.out.println("Unsorted Input List: " + list.toString());
       PQ priorityQueue = new PQ(list);
       List<Integer> sortedList = priorityQueue.toSortedList();
       System.out.println("Sorted List Descending order: " + sortedList.toString());

   }

   private static List<Integer> randomList(int size){

       final Random rng = new Random();

       List<Integer> list = new ArrayList<>(size);

       for(int i = 0; i< size; i++){

       list.add(rng.nextInt()%10);

       }

       return list;

   }
}

//end of PQAssignment.java

Output: