tailieunhanh - ShortestParths

We call it a priority queue - but its not FIFO Items in queue have PRIORITY. Elements are removed from priority queue in either increasing or decreasing priority. Min Priority Queue. Max Priority Queue P=2 P=5 P=1 P=25 P=9. | Bonus Topic: Priority Queue The Priority Queue We call it a priority queue - but its not FIFO Items in queue have PRIORITY Elements are removed from priority queue in either increasing or decreasing priority Min Priority Queue Max Priority Queue P=2 P=5 P=1 P=25 P=9 The Priority Queue Consider situation where we have a computer whose services we are selling Users need different amounts of time Maximise earnings by min priority queue of users . when machine becomes free, the user who needs least time gets the machine; the average delay is minimised P=2 P=5 P=1 P=25 P=9 Next user chosen will be The Priority Queue Consider situation where users are willing to pay more to secure access - they are in effect bidding against each other Maximise earnings by max priority queue of users . when machine becomes free, the user who is willing to pay most gets the machine P=2 P=5 P=1 P=25 P=9 Next user chosen will be The Priority Queue Common data structure in computer science Responsible | Bonus Topic: Priority Queue The Priority Queue We call it a priority queue - but its not FIFO Items in queue have PRIORITY Elements are removed from priority queue in either increasing or decreasing priority Min Priority Queue Max Priority Queue P=2 P=5 P=1 P=25 P=9 The Priority Queue Consider situation where we have a computer whose services we are selling Users need different amounts of time Maximise earnings by min priority queue of users . when machine becomes free, the user who needs least time gets the machine; the average delay is minimised P=2 P=5 P=1 P=25 P=9 Next user chosen will be The Priority Queue Consider situation where users are willing to pay more to secure access - they are in effect bidding against each other Maximise earnings by max priority queue of users . when machine becomes free, the user who is willing to pay most gets the machine P=2 P=5 P=1 P=25 P=9 Next user chosen will be The Priority Queue Common data structure in computer science Responsible for scheduling jobs Unix (linux) can allocate processes a priority Time allocated to process is based on priority of job Priority of jobs in print scheduler Priority Queue Priority Queue The elements in a stack or a FIFO queue are ordered based on the sequence in which they have been inserted. In a priority queue, the sequence in which elements are removed is based on the priority of the elements. A Priority=1 B Priority=2 C Priority=3 D Priority=3 Ordered Priority Queue (highest priority) (lowest priority) B Priority=2 C Priority=3 A Priority=1 D Priority=3 Unordered Priority Queue The first element to be removed. Priority Queue Priority Queue - Array Implementation To implement a priority queue using an array such that the elements are ordered based on the priority. Time complexity of the operations : (assume the sorting order is from highest priority to lowest) Insertion: Find the location of insertion. O(__) Shift the elements after the location O(__) where n = number of elements