CSCI 3320 – Programming Assignment#2
CSCI 3320 Programming Assignment 2
(Due: 11:59 PM, Sunday, Nov 27, 2016)
Implementation of D-Heaps
The binary heap discussed in class is a special case of a d-heap with d=2. Write the methods for
1. deleteMin (and percolate down)
2. insert
3. buildHeap
for a d-heap. Use an array to implement the d-Heap in a similar manner to the definition of the BinaryHeap data structure given in Figure 6.4 of the Weiss book. ‘d’ should now be an private integer data member of the DHeap class. You should read the heap elements and ‘d’ from the console and print the output in the following manner:
(Note: Do not take the initial elements one at a time).
Enter heap elements: 12 13 11 4 7 9 3 15 8 5 6 14 2
Enter d: 3
Output: Heap (d=3): 2 3 5 4 7 9 13 15 8 11 6 14 12
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 1
Enter element to insert: 1
Output: Heap (d=3): 1 2 5 4 3 9 13 15 8 11 6 14 12 7
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 1
Enter element to insert: 10
Output: Heap (d=3): 1 2 5 4 3 9 13 15 8 11 6 14 12 7 10
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 2
Output: Heap (d=3): 2 3 5 4 7 9 13 15 8 11 6 14 12 10
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 3
Enter d: 2
Output: Heap (d=2): 2 3 5 4 6 9 10 15 8 11 7 14 12 13
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 4
Program Terminated
The sample given was a simple heap up to 15 elements. Your program will be tested with a larger heap and different d values.
Note: Source code from the Weiss book can be found here
Deliverables: An electronic copy of your source files with brief compiling and running instructions should be submitted through the Blackboard server (Make a single zipped file from all the files to submit).
Note that your code should be tested on the loki.ist,unomaha.edu machine.
For full credit, your code should be well documented with comments, and the style
of your code should follow the following guidelines:
Your programs must contain enough comments. Programs without comments or with insufficient and/or vague comments will cost you up to 30%.
Every file should have a comment header describing who wrote the program and what is in the file. An example header comment is shown below:
/***************************************************
* Program Title: XXXXXXXXXXXXXXXXXXXXXX *
* Author: XXXXX XXXXXX *
* Class: CSCIXXXX, Fall 201X
*
* Assignment #2
*
****************************************************/
Every method or function should have a comment header describing inputs, outputs, and what it does. An example function comment is shown below:
/***************************************************
* FUNCTION xxyyzz : (function name)
*
* the purpose of this function
*
* INPUT PARAMETERS :
* * a list of all parameters and their meaning *
* OUTPUT :
* * the description about returning value *
****************************************************/
Inline comments should be utilized as necessary (but not overused) to make algorithms clear to the reader.
Not-compile programs may receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, incorrect filenames, syntax errors in your programs, and so on. Double check your files before you submit, since I will not change your program to make it work.
Compile-but-not-run programs receive no more than 50%. Compile-but-not-run means you have attempted to solve the problem to certain extent but you failed to make it working properly. A meaningless or vague program receives no credit even though it compiles successfully.
Programs delivering incorrect result, incomplete result, or incompatible output receive no more than 70%
Test Case:
Enter heap elements: 15 1 14 2 13 3 12 4 11 5 10 6 9 7 8
Enter d: 3
Output: Heap (d=3): 1 3 4 2 7 15 12 14 11 5 10 6 9 13 8
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 1
Enter element to insert: 0
Output: Heap (d=3): 0 1 4 2 3 15 12 14 11 5 10 6 9 13 8 7
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 2
Output: Heap (d=2): 1 3 4 2 7 15 12 14 11 5 10 6 9 13 8
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 2
Output: Heap (d=2): 2 3 4 6 7 15 12 14 11 5 10 8 9 13
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 3
Enter d: 2
Output: Heap (d=2): 2 3 4 6 5 8 12 14 11 7 10 15 9 13
Press 1) for insert, 2) for deleteMin, 3) for new d value, 4) to quit
Enter choice: 4
Program Terminated