CP164 Lecture Notes - Lecture 7: Priority Queue
Document Summary
Once item is added remove function does most work ( it must find the next item with highest priority. Insertion may be expensive if we sort. For this lab we will make remove function do the most work. Lower case__first to state it to only be used within the queue definition. Look similar to standard queue insert for priority queue. Walk through python list and look for smallest value==highest priority. Don care what the value is, only where it is. Priority queue are good for things called greedy algorithms. Are base stations must be connected into system so it doesn"t matter which one you start with. Start a priority queue to keep track of all connects (if you start at a, add all connected to a-b, a-c,a-d) Go to queue and ask give me the next cheapest connection. If equal we pick the one that went in priority queue first ( by order of entry)
