Posted: November 4th, 2015

Data structure assignment using C++ (programming)

Description:
Scheduling is an NP-hard optimization problem. However, it is applicable in a vast number of fields and situations. An often used heuristic for this problem is the Longest Processing Time algorithm. You are required to implement the Longest Processing Time algorithm as follows. Your algorithm will be implemented in two versions using two different representations of a minimum priority queue. The first implementation will use an array-based  min-heap. The second implementation will use a pointer-based min height-biased leftist tree.

For both implementations of your Min Priority Queue data structure, you must implement a constructor, destructor, empty, size, push, top, and pop functions. You may also implement any helper function(s) at your own discretion.

  • The meld function of your leftist heap implementation must be recursive.
  • The empty function returns a bool of whether or not the priority queue is empty.
  • The size function returns the current number of elements in the priority queue.
  • The push function inserts an element into the priority queue.
  • The top function returns the element with the min priority.
  • The pop function removes the element with the min priority.

You will run the dataset on each version and output the finishing time.
The program will also print the schedule.

 

 

 

Sample input and output (User Input is represented in REDfont ):

 

Enter number of job(s):
7
Enter number of machine(s):
3
Enter Processing Time(s):
14
7
10
6
2
3
5

Min Heap Finishing Time: 16
Schedule:
Machine 1: 14, 2

Machine 2: 10, 5

Machine 3: 7, 6, 3
Time Elapsed:3.882e-06

 

Height Biased Leftist Tree Finishing Time: 16

Schedule:

Machine 1: 14, 2

Machine 2: 10, 5

Machine 3: 7, 6, 3
Time Elapsed: 3.927e-06
Note: Your elapsed times will likely differ from these.

You are not allowed to use any heap or leftist tree facilities in the C++ STL.

 

Expert paper writers are just a few clicks away

Place an order in 3 easy steps. Takes less than 5 mins.

Calculate the price of your order

You will get a personal manager and a discount.
We'll send you the first draft for approval by at
Total price:
$0.00
Live Chat+1-631-333-0101EmailWhatsApp