Đang chuẩn bị liên kết để tải về tài liệu:
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 i.e. 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 i.e. 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 i.e. 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 i.e. 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