I have to write a program in c that implements binary heaps. I am not too sure w

Question

I have to write a program in c that implements binary heaps. I am not too sure where to start.

Objective By completing this assignment, students will demonstrate a working knowledge of the following Binary Heap concepts: 1. Code implementation of BH 2. Traversing BH 3. Algorithm for inserting nodes into a BH 4. Deleting nodes from a BH 5. Searching for values in BH
Problem: Managing the Printer Queue You are working as an intern at the GreenPrinters Company. Your job is to write the software to program the ‘printing job spooling functionality’ of the latest printer model.   Your code should be able to: 1. Read jobs one at a time from a file and add them to a binary heap ordered on the priority of the job (the lower the priority number, the higher the priority)- Example 8 has higher priority than 15. 2. Service the jobs in the queue each in its turn while maintaining the integrity of the BH a. Servicing a job means that this job is deleted from the queue
Each Job is comprised of the following information: The name of the file to be printed (no more than 35 characters) The priority of the job (a positive integer)
When run, your program should read a batch file of jobs. Each line of the file contains information about 1 job as described in the input file structure section.
If a job is waiting in the batch file (meaning that its arrival time is before or equal to the current time), your printer will en-queue that job before printing the next job. Otherwise your printer will print the next job. The time stamp is implemented as a simple integer. When the program begins that is time 0, the next operation will be at time 1 etc.
A success message will be output to the output file each time a job has been successfully enqueued. A list of the waiting jobs will also be printed as shown in the sample output.    When a job is printed, a message is output indicating the name of the file that has been printed and the time. This is followed by a list of the names of the files still waiting in the printing queue. If no job is waiting in the queue and there is no job in the batch file at that time, your printer will print a Ready message. For the sake of simplicity you may assume that at any time, the printer can either print a job or en-queue a job–but not both.
2
Structure of the inputfile (jobs.txt) The input file contains a set of jobs each on a separate line. A line begins with an integer indicating the arrival time of the job, followed by a string indicating the file name.    The line ends with a positive integer indicating the priority of the job.
Output Specification
Your output should match that in the sample output. You are to use the exact text. Do not change the response text.    
Implementation Restrictions a. The file names have no spaces b. Your output file should be called output.txt c. Your program should expect an input file called jobs.txt d. If 2 jobs of the same priority are on the queue, the first job to arrive is processed first  

Sample Input File
0 Exam2.pdf 4

1 FacialRecognitionSystems.pdf 2

4 ComputerGraphics.cgl   5

6 DenotationalSemantics.c 1

7 Input.in   3

8 ClassList.txt 2       
3
Sample Output File (output.txt)

Time 0

---------

Exam2.pdf has been added to the queue
Exam 2 is waiting to be printed  

Time 1

--------

Facial Recognition Systems.pdf has been added to the queue
Facial Recognition Systems.pdf Exam 2.pdf Are waiting to be printed  

Time 2

---------

Facial Recognition Systems.pdf has been printed
Exam 2.pdf is waiting to be printed  

Time 3

---------

Exam 2.pdf has been printed
Printer is ready  

Time 4

--------

ComputerGraphics.cgl has been added to the queue
ComputerGraphics.cgl is waiting to be printed  

Time 5

---------

ComputerGraphics.cgl has been printed
Printer is ready
4

Time 6

--------

DenotationalSemantics.c has been added to the queue
DenotationalSemantics.c is waiting to be printed  

Time 7

--------

Input.in has been added to the queue
DenotationalSemantics.c Input.in    are waiting to be printed  

Time 8

---------

ClassList.txt has been added to the queue
DenotationalSemantics.c

ClassList.txt  

Input.in   

are waiting to be printed  

Time 9

--------

DenotationalSemantics.c has been printed
ClassList.txt  

Input.in   

are waiting to be printed  

Time 10

--------

ClassList.txt has been printed
Input.in   

is waiting to be printed    
5

Time 11

--------

Input.in has been printed
Printer is ready

Explanation / Answer

package DataStructures; // BinaryHeap class // // CONSTRUCTION: with optional capacity (that defaults to 100) // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // Comparable deleteMin( )--> Return and remove smallest item // Comparable findMin( ) --> Return smallest item // boolean isEmpty( ) --> Return true if empty; else false // boolean isFull( ) --> Return true if full; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Throws Overflow if capacity exceeded /** * Implements a binary heap. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ public class BinaryHeap { /** * Construct the binary heap. */ public BinaryHeap( ) { this( DEFAULT_CAPACITY ); } /** * Construct the binary heap. * @param capacity the capacity of the binary heap. */ public BinaryHeap( int capacity ) { currentSize = 0; array = new Comparable[ capacity + 1 ]; } /** * Insert into the priority queue, maintaining heap order. * Duplicates are allowed. * @param x the item to insert. * @exception Overflow if container is full. */ public void insert( Comparable x ) throws Overflow { if( isFull( ) ) throw new Overflow( ); // Percolate up int hole = ++currentSize; for( ; hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 ) array[ hole ] = array[ hole / 2 ]; array[ hole ] = x; } /** * Find the smallest item in the priority queue. * @return the smallest item, or null, if empty. */ public Comparable findMin( ) { if( isEmpty( ) ) return null; return array[ 1 ]; } /** * Remove the smallest item from the priority queue. * @return the smallest item, or null, if empty. */ public Comparable deleteMin( ) { if( isEmpty( ) ) return null; Comparable minItem = findMin( ); array[ 1 ] = array[ currentSize-- ]; percolateDown( 1 ); return minItem; } /** * Establish heap order property from an arbitrary * arrangement of items. Runs in linear time. */ private void buildHeap( ) { for( int i = currentSize / 2; i > 0; i-- ) percolateDown( i ); } /** * Test if the priority queue is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return currentSize == 0; } /** * Test if the priority queue is logically full. * @return true if full, false otherwise. */ public boolean isFull( ) { return currentSize == array.length - 1; } /** * Make the priority queue logically empty. */ public void makeEmpty( ) { currentSize = 0; } private static final int DEFAULT_CAPACITY = 100; private int currentSize; // Number of elements in heap private Comparable [ ] array; // The heap array /** * Internal method to percolate down in the heap. * @param hole the index at which the percolate begins. */ private void percolateDown( int hole ) { /* 1*/ int child; /* 2*/ Comparable tmp = array[ hole ]; /* 3*/ for( ; hole * 2

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---