C++ Implement a node class and priority queue to contain items of the node class. This must include Insert(), Peek(), Extract(), and ChangeKey() implementation.

insert(x) inserts the node x into the priority queue. peek() returns the node with the largest or smallest key, depending on the type of queue. extract() removes and returns the element of S with the largest or smallest key, depending on the type of queue. changeKey(i, k) changes the value of the key of the element located at index i in the heap array to the new value k, then swaps the key up the heap until it is in the correct place.

Using HeapSort implementation and the example code template given below

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.

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.