Assignment 3 Heap data structure

 Assignment 3—programming

Objectives  Heap data structure  Priority queues  Heapsort  Random number generation
Programming Assignment You are to implement a java class PQ225 to practice designing, implementing and testing priority queues with the following objectives:
Fields An integer array, heapArray
Constructors PQ225()
Methods Part 1: Random Number Generation Design and implement a java method ranGen() from scratch that generates uniform integer random numbers.
Return Type Method Description void ranGen(int N, int LOW, int HIGH)
generates N random numbers in the range LOW to HIGH and inserts them into the heapArray
Implement your generator using the following pseudo code:

Part 2: Building up a heap in linear time Return Type Method Description int size() returns size of the array in O(1)
void insert(int i) inserts an integer i into the heap in O(log n) time int deleteMin() delete the smallest integer from the heap in O(log n) time
void makeHeap() turns the unsorted integer array, heapArray into a heap in O(n)
Part 3: HeapSort in O(n log n) Implement In Place Heap Sort.
Return Type Method Description int heapsort() sorts the integer array, heapArray, using In Place Heap Sort in O(n log n). Use methods from Part 2. (Nothing specific to return, you can use it for testing)
Procedure ranGen(N, LOW, HIGH): //populate heapArray with random values 𝑠𝑒𝑒𝑑 ← 𝑠𝑦𝑠𝑡𝑒𝑚𝐶𝑙𝑜𝑐𝑘( ) 𝑘 ← 0 𝑤ℎ𝑖𝑙𝑒 𝑘 < 𝑁 𝑑𝑜: //𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒 𝑎 𝑟𝑎𝑛𝑑𝑜𝑚 𝑛𝑢𝑚𝑏𝑒𝑟 𝑟𝑛 𝑑𝑜 𝑟𝑛 ← 𝑟𝑎𝑛𝑑( ) 𝑤ℎ𝑖𝑙𝑒 𝑟𝑛 < 𝐿𝑂𝑊 𝑜𝑟 𝐻𝐼𝐺𝐻 < 𝑟𝑛: ℎ𝑒𝑎𝑝𝐴𝑟𝑟𝑎𝑦[𝑘] ← 𝑟𝑛 𝑘 ← 𝑘 +1 End Procedure

Part 4: Testing of Priority Queues Return Type Method Description void test() Tests and exercises the methods developed for the first three parts of this assignment extensively. The output generated by this class must convince the marker that the classes are implemented as specified. For example:  Generate heaps of different sizes (e.g., 100, 1000, 10000).  Implement a test that checks whether heapsort sorts properly.  Measure the performance of heapsort, by counting comparisons for inputs of different length.  Chart the performance on a graph!
Your code must also print out results out into a textfile called pq_test.txt This text file must have a short description what your test cases are and along with the results. You have flexibility to decide and choose how extensively you want to test your methods.