Write the main java program to read all records from inventory.txt to build a Maxheap Queue using MaxHeap.java. At the end, remove the Max from Maxheap queue and print the Maxheap. The order of the priority is the string value of the input records.

Maxheap.java

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

import java.lang.Comparable;

/** Max-heap implementation */ public class MaxHeap> { private E[] Heap; // Pointer to the heap array private int size; // Maximum size of the heap private int n; // Number of things in heap

/** Constructor supporting preloading of heap contents */ public MaxHeap(E[] h, int num, int max) { Heap = h; n = num; size = max; buildheap(); }

/** @return Current size of the heap */ public int heapsize() { return n; }

/** @return True if pos a leaf position, false otherwise */ public boolean isLeaf(int pos) { return (pos >= n/2) && (pos < n); }

/** @return Position for left child of pos */ public int leftchild(int pos) { assert pos < n/2 : "Position has no left child"; return 2*pos + 1; }

/** @return Position for right child of pos */ public int rightchild(int pos) { assert pos < (n-1)/2 : "Position has no right child"; return 2*pos + 2; }

/** @return Position for parent */ public int parent(int pos) { assert pos > 0 : "Position has no parent"; return (pos-1)/2; }

/** Insert val into heap */ public void insert(E val) { assert n < size : "Heap is full"; int curr = n++; Heap[curr] = val; // Start at end of heap // Now sift up until curr's parent's key > curr's key while ((curr != 0) && (Heap[curr].compareTo(Heap[parent(curr)]) > 0)) { DSutil.swap(Heap, curr, parent(curr)); // exchange content of Heap[curr] with Heap[parent(curr)] curr = parent(curr); } } /** Heapify contents of Heap */ public void buildheap() { for (int i=n/2 - 1; i>=0; i--) siftdown(i); }

/** Put element in its correct place */ private void siftdown(int pos) { assert (pos >= 0) && (pos < n) : "Illegal heap position"; while (!isLeaf(pos)) { int j = leftchild(pos); if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0)) j++; // j is now index of child with greater value if (Heap[pos].compareTo(Heap[j]) >= 0) return; DSutil.swap(Heap, pos, j); pos = j; // Move down } }

/** Remove and return maximum value */ public E removemax() { assert n > 0 : "Removing from empty heap"; DSutil.swap(Heap, 0, --n); // Swap maximum with last value if (n != 0) // Not on last element siftdown(0); // Put new heap root val in correct place return Heap[n]; }

/** Remove and return element at specified position */ public E remove(int pos) { assert (pos >= 0) && (pos < n) : "Illegal heap position"; if (pos == (n-1)) n--; // Last element, no work to be done else { DSutil.swap(Heap, pos, --n); // Swap with last value // If we just swapped in a big value, push it up while ((pos > 0) && (Heap[pos].compareTo(Heap[parent(pos)]) > 0)) { DSutil.swap(Heap, pos, parent(pos)); pos = parent(pos); } if (n != 0) siftdown(pos); // If it is little, push down } return Heap[n]; } }

Inventory.txt

CV06C1250B MA06C1042A MA06C1043A SU04D1043B SU04D1042B CV06C1250A CV06D1250B HY09F3014A KI04D1297A

Dsutil.java

/** Source code example for "A Practical Introduction to Data Structures and Algorithm Analysis, 3rd Edition (Java)" by Clifford A. Shaffer Copyright 2008-2011 by Clifford A. Shaffer */

import java.util.*; import java.math.*;

/** A bunch of utility functions. */ class DSutil {

/** Swap two Objects in an array @param A The array @param p1 Index of one Object in A @param p2 Index of another Object A */ public static void swap(E[] A, int p1, int p2) { E temp = A[p1]; A[p1] = A[p2]; A[p2] = temp; }

/** Randomly permute the Objects in an array. @param A The array */

// int version // Randomly permute the values of array "A" static void permute(int[] A) { for (int i = A.length; i > 0; i--) // for each i swap(A, i-1, DSutil.random(i)); // swap A[i-1] with } // a random element

public static void swap(int[] A, int p1, int p2) { int temp = A[p1]; A[p1] = A[p2]; A[p2] = temp; }

/** Randomly permute the values in array A */ static void permute(E[] A) { for (int i = A.length; i > 0; i--) // for each i swap(A, i-1, DSutil.random(i)); // swap A[i-1] with } // a random element

/** Initialize the random variable */ static private Random value = new Random(); // Hold the Random class object

/** Create a random number function from the standard Java Random class. Turn it into a uniformly distributed value within the range 0 to n-1 by taking the value mod n. @param n The upper bound for the range. @return A value in the range 0 to n-1. */ static int random(int n) { return Math.abs(value.nextInt()) % n; }

}