Assignment 3 Programming Part Solution

$30.00 $26.40

Description

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:

Procedure ranGen(N, LOW, HIGH):

//populate heapArray with random values

← ( )

← 0

ℎ < :

//

← ( )

ℎ < < :

ℎ [ ] ←

← + 1

End Procedure

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)

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.