JAVA:

Using HeapSort implementation and the example code template given below, implement a node class and priority queue to contain items of the node class. The node class should have instance variables that define an ID and a key. It should also have a compare method that can be adjusted to make the queue either min or max priority. The priority queue implementation should extend the heap class by adding the additional methods listed above. You should also add a location table to the heap. The location table keeps track of the location of each node in the heap by ID.

HeapSort implementation:

class HeapSort implements Sortable{ public int[] arr; private int heapsize; private int elements; private String type;

public HeapSort(int elements, String randomOrSorted){ arr = new int[elements]; type=randomOrSorted; this.elements=elements; this.heapsize=elements; if(randomOrSorted==("Random")){ for(int n=0; narr[largest]){ largest = left; } if(rightarr[largest]){ largest = right; } if(largest!=i){ arr[i] = arr[i] - arr[largest]; arr[largest]= arr[i] + arr[largest]; arr[i]= arr[largest] - arr[i]; maxHeapify(largest); } }

public void buildMaxHeap(){ for(int i=heapsize/2-1; i>=0; i--){ maxHeapify(i); } } public void show(){ for(int i=0;i0; j--){ arr[0] = arr[0] - arr[j]; arr[j]= arr[0] + arr[j]; arr[0]= arr[j] - arr[0]; heapsize--; maxHeapify(0); } long stop = System.nanoTime(); System.out.println(elements + " " + type + " elements: " + (stop-start) + " ns"); } }

Program code template: public class Node implements Comparable { public int ID; public int key; public Node(int ID, int key) { // code } @Override public int compareTo (Node node2) { // code } } public class Heap { protected Node[] heap; protected int heapsize; protected int[] location; public Heap() { // create a heap with a default size, 20 } public Heap(int n) { // create a heap of size n }

public Heap(Node[] a) { // create a heap from an array of nodes } public int parent(int i) { // code } public int left(int i) { // code } public int right(int i) { // code } public void heapify(int i) { // code } public void buildheap() { // code } } public class PriorityQueue extends Heap{ public PriorityQueue(int maxsize) { // create a priority queue of size maxsize } public void insert(Node newNode) { // code } public Node peek() { // code } public Node extract() { // code } public void changeKey(int i, int k) { // code } } public class Main { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(7);

pq.insert(new Node(0,3)); pq.insert(new Node(1,14)); pq.insert(new Node(2,7)); pq.insert(new Node(3,9)); pq.insert(new Node(4,99)); pq.insert(new Node(5,2)); pq.insert(new Node(6,46)); for (int i = 0; i < 7; i++) { System.out.print(pq.extract().key + " "); } } }

The above code should print out 99 46 14 9 7 3 2

For use in troubleshooting: The heap should contain 99 14 46 3 9 2 7 The location table should contain 3 1 6 4 0 5 2

The code should work correctly for any input and size.