CS 3310 Spring 2024
Assignment 4
Priority Queues
Objectives
Assignment 4
Covid Vaccine Patient List
Release Date
Due Date
•
Understand the concepts and application of binary heap
•
Understand the concepts and application of priority queue
•
Understand the concepts and application of linked list
•
Practice developing high-performance solutions
•
•
Understand at times somewhat vague, requirements to develop a computing application
Design and develop different solutions to a computing problem
Problem Specification
You are contacted by Sindecuse Health Center, and they want your help to manage the patient list for covid
vaccine. As per the suggestion of Centers for Disease Control and Prevention (CDC), Sindecuse wants to
provide vaccine first to those who need them most. For this purpose, Sindecuse already created a rating
system based on different factors, like their job (if frontline workers or work from home employee, etc.), age
group, underlying medical condition and many other factors and assigned each registered patient a number
between 1 to 10, where 10 means highest priority patient and 1 means lowest priority patient in terms of covid
vaccine.
Now, they want you to write a program that will run through Sindecuse patient database and provide them with
a patient list based on their priority number where a patient with highest priority will be on top so that s/he can
get the vaccine first. And this is where priority queue comes in handy. In many real-life scenarios queue data
structure (FIFO) are very helpful and reasonable for example, customer call center -- where they response to
call in the order as they were received, restaurants - where customer who is first in the line is the one to be
served first. But that is not always the case. For example: in hospital emergency room, patient needs to be
served based on their emergency priority. And in cases like this, a priority-queue comes handy.
Sindecuse provided you two different input files, 'priority.txt' and 'patient_info.txt'. In 'priority.txt' file you have 2
columns, 'Priority' and 'Patient ID', where rating is a number between 1 to 10 (inclusive), and patient id is the
Sindecuse representation of each patient, same as your WIN for Western Michigan University. And second file,
'patient_info.txt', contains, 3 rows, 'Patient ID', 'Full Name', and 'Contact Number'.
1 CS 3310 Spring 2024
Assignment 4
Priority Queues
As a Software Engineer Entrepreneur you were awarded a contract from Sindecuse, your job is to write
an application that performs following tasks:
1) Read each row from the given input file "priority.txt", and then store all the data in a max-priority queue.
Implement the priority queue PQ using a linked list. While setting this up, use rating as key and patient id
as value for the priority queue. Note, we will have to allow duplicates in PQ.
2) Now read each row from the second input file, 'patient_info.txt' and store all the information in another
linked list. While storing data, use patient id as key.
3) Now, our data structures are ready. So, we will start taking each entry (high priority to low priority) from the
max-priority queue that we created in step 1. And, get the patient id, and using that patient id, we will
search in the other linked list and then print the patient's information in the given format.
NOTE: Don't Hardcode any data or value except file names.
Sample output
Patient ID: XXXXXXX
Full Name: aaaaaa bbbbbbb
Priority: Y
Contact Number: kkkkkkkkkk
Patient ID: XXXXXXX
Priority: Y
Full Name: aaaaaa bbbbbbb
Contact Number: kkkkkkkkkk
Output Requirements
•
•
Print information for all the patients from the given input file in the above format.
Print patient's information from high priority towards low priority. That means, information of a patient
with the highest priority will be printed first and second highest next and so on.
Now replace the linked list used as a priority queue with a binary heap and replace the linked list you
used to search with a binary search tree (BST). NOTE: Please DO NOT use built-in library data
structures. Develop your own.
What is the tradeoff between using linked list/linked list and heap/BST in terms of time complexity? Generate a
report showing the execution times of both and explaining this question. We can use a binary heap and a BST
to sort. Repeatedly deleting the highest priority item from the binary heap yields heap-sort, while an in-order
traversal of BST yields BST-sort. The program goes through the binary heap in decreasing sort order already.
But, you will need to create a method that implements an in-order traversal of the BST. Display the time it
takes to perform the heap-sort and the BST-sort with this output:
2 CS 3310 Spring 2024
Time for heap-sort: xxxx nanoseconds
Time for BSTsort: xxxx nanoseconds
Assignment 4
Priority Queues
Design Requirements
Coding Conventions and Programming Standards
You must adhere to programming styles and conventions from your CS1 and CS2 courses this includes the
use of white spaces for readability and the use of comments to explain the meaning of various methods,
attributes, and logic.
Assignment Submission
•
Generate a .zip file that contains all your files, including:
■ Source code files
"
Any input or output files
3
