In: Computer Science
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 | |
} | |
} |
// 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: