Please look at these questions

Running head: CISC610 ASSIGNMENT 1 1

Example of Priority Queue

Use case 1 – hospital waiting room waiting list

One use (application) of PQ could be the waiting queue in the hospital patient waiting room (Cha, 2018a & Lam, 2016). It is common sense that patient should be treated on their illness severity (hurt level) (Lam, 2016) instead of the time (order they come in). This hurt level can be assigned as the priority key value. And we can put all the patient in waiting room into a priority queue, and more specifically, a Binary Heap. With the patient who is most hurt on the front of the queue, that is the root of the queue which has highest priority (key) value.

Creation operation

When new patient coming in, a key (priority) value is assigned to him (or her), and this number represents the patient’s hurt level, the higher the number is, the more hurt the patient has, and the higher priority he (or she) needs to be treated (exit from the queue). First patient is added it into the queue (initially at the root), with more patients come in, all patients in waiting room are added into the Heap, as shown in Figure 1. As we can see this Binary Heap has been already heapified, all nodes other than a leaf has higher or equal key value than its children.

Figure 1 hospital patient waiting room priority queue (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Remove operation

Then the patient will be treated from highest key value to lowest key value, this means he/she will be removed from the queue, and this actually is the Remove operations which is demonstrated in below steps:

1. Patient-16 (we give patient ID as patient-its key value) is treated, meaning removed to the queue, shown in Figure 2.

Figure 2 Remove root item (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Then the next patient who now has highest key value should be in the front (root) of the queue, these are done through the operation shown in Figure 3 to 6 (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Figure 3 Put last in root position (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Figure 4 Swap root and its larger children (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Figure 5 reheap towards achieving heap priority (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Figure 6 Finally achieved heap priority (Cha, 2018b & Laakso, M., Korhonen., A & Karavirta, V. 2011)

Add operation

If a new patient comes in and the queue is not full yet, a priority (hurt level) value (for example value 15) will be assigned to him, and it will be put into the correct position into the queue, so the help property will be maintained. The Add operation is achieved through steps shown in Figure 7 to 9 (Cha, 2018b & Gunes, M.H, 2016).

Figure 7 assign key (priority) value to new patient, initialize adding of it (Cha, 2018b & Gunes, M.H, 2016)

Figure 8 Adding: try different position (Cha, 2018b & Gunes, M.H, 2016)

Figure 9 Adding: Found correct position (Cha, 2018b & Gunes, M.H, 2016)

Full and Empty operation

These two operations are quite straight-forward: if the maximum waiting patients reaches the maximum number, the queue is full and no more patient is added. If all patients have been treated and no more new patient come in, the queue is Empty.

Use case 2 – Dijkstra's algorithm

Introduction

Dijkstra’s algorithm is an algorithm to find the shortest path from the start node (Abiy, T., & Pang, H., & Wilkiams, C, NA) “to a target node” (Abiy, T., & Pang, H., & Wilkiams, C, NA) and “creates a tree of shortest paths from the start node to all other points in the graph” ((Abiy, T., & Pang, H., & Wilkiams, C, NA).

How the use case apply the priority queue

Dijkstra’s Algorithm (DA) assign a distance value (iyappan, 2017), or effort between different nodes, then finds the shortest path from starting node to adjacent nodes, and assign the cloest vertex as next start node (iyappan, 2017 & Barngrader, 2014) , the repeat above two steps, until reach the destination (iyappan, 2017). As each sub-path has is the shortest, the final path from start to destination is also shortest. DA applies Priority Queue (PQ) applies in below ways:

a. The distance between nodes in DA is like the priority (key) value in PQ

b. the smaller the distance in DA is like the higher priority of the key value in PQ

c. The shortest node is firstly taken into the path, this is like the item with the highest priority value is moved out in PQ

How Dijkstra’s Algorithm works

The steps are depicted in below Figures. Step-1 in Figure 10: list the distance from starting point A to its adjacent node, and mark them as 8A, 2A, 5A respectively for B, C, D (Barngrader, 2014). The small character after the distance means via the corresponding node. And for other non-adjacent nodeS to A, give the distance as infinity (Barngrader, 2014). C is the shortest to A, so copy its distance to next line and now put C as second start node, and mark C with a square box, as no need to consider C again, as it’s the shortest path to A (Barngrader, 2014).

Figure 10 From A to its adjacent nodes (Barngrader, 2014)

Step-3: As shown in Figure 11. B is not adjacent to B, so copy A underneath B distance (8A) to C line. The extra distance from C->D plus distance between A->C is less than A->D, so change 5A to 4C for D. Then repeat steps in Figure 1 (Barngrader, 2014).

Figure 11 From C to its adjacent nodes (Barngrader, 2014)

Step-4: As shown in Figure 12, D is the next shortest path, so put a box (square) around 4C, and now D is the next node to consider, that is, to look at the distance from D to all its adjacent node. Find a short path of A->C->D->B with distance of 6, so change 8A to 6D. Same happens to E, so change 7C to 5D. Then same applies to F and G (Barngrader, 2014).

Figure 12 From D to its adjacent nodes (Barngrader, 2014)

Step-5: As shown in Figure 13. E is the next shortest node to consider, and repeat above steps.

Figure 13 From E to its adjacent nodes (Barngrader, 2014)

Step-9: As shown in Figure 14, repeat all above steps for left node and find shortest path to its adjacent node, now we can below final result: the shortest path from A to all other nodes are found now (Barngrader, 2014). For example: from A to H, the shortest path is deducted as below: see the shortest is via F in column H, then see the shortest is via G in column F, then see in the shortest is via E in column G, to via D, via C and A, so the shortest path from A to H is this: A--2->C--2->D--1->E--1->G--2->F--3->H. Using this way, can find the shortest path from A (actually from any node) to any other node (Barngrader, 2014).

Figure 14 From H to its adjacent nodes (Barngrader, 2014)

Add, Remove operations in Dijkstra’s Algorithm

Creation operation have been covered in above sections. If a node is removed, all the path to its adjacent nodes are to be removed. If a new node is added, path to its adjacent nodes need to be added. In both of the cases, it need to re-exam the shortest path.

References

Abiy, T., & Pang, H., & Wilkiams, C. (NA). Dijkstra’s Shortest Path Algorithm. Retrieved from https://brilliant.org/wiki/dijkstras-short-path-finder/

Barngrader. (2014, Nov 14). Dijkstra’s Algorithm: Another example. Retrieved from https://www.youtube.com/watch?v=5GT5hYzjNoo

Cha, S. (2018, June 29). E-mail with student.

Cha, S. (2018, June). CISC610-50 Unit 5 class presentation. Retrieved from https://moodle.harrisburgu.edu/course/resources.php?id=5362

Gunes, M. H. (2016). Chapter 17. Heaps. CS 302 – Data Structures Lecture Slide, University of Nevada, Reno.

Iyappan. (2017, July 6). Dijkstra’s Rules – Graph: Dijkstra’s Algorithm with Animation (Shortest Path Search). Retrieved from https://www.youtube.com/watch?v=Lfb8qkXzHY0

Laakso, M., Korhonen., A & Karavirta, V. (2011, May 30). Priority Queues and Binary Heap - Delete Max. Department of Computer Science, Aalto University. Retrieved from http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/poistaminen.html