Question? Leave a message!




Abstract Priority Queues

Abstract Priority Queues
ECE 250 Algorithms and Data Structures Abstract Priority Queues Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Abstract Priority Queues 2 Outline This topic will: – Review queues – Discuss the concept of priority and priority queues – Look at two simple implementations: • Arrays of queues • AVL trees – Introduce heaps, an alternative tree structure which has better runtime characteristicsAbstract Priority Queues 3 7.1 Background We have discussed Abstract Lists with explicit linear orders – Arrays, linked lists, strings We saw three cases which restricted the operations: – Stacks, queues, deques Following this, we looked at search trees for storing implicit linear orders: Abstract Sorted Lists – Run times were generally Q(ln(n)) We will now look at a restriction on an implicit linear ordering: – Priority queuesAbstract Priority Queues 4 7.1.1 Definition With queues – The order may be summarized by first in, first out If each object is associated with a priority, we may wish to pop that object which has highest priority With each pushed object, we will associate a nonnegative integer (0, 1, 2, ...) where: – The value 0 has the highest priority, and – The higher the number, the lower the priorityAbstract Priority Queues 5 7.1.2 Operations The top of a priority queue is the object with highest priority Popping from a priority queue removes the current highest priority object: Push places a new object into the appropriate placeAbstract Priority Queues 6 7.1.3 Lexicographical Priority Priority may also depend on multiple variables: – Two values specify a priority: (a, b) – A pair (a, b) has higher priority than (c, d) if: • a c, or • a = c and b d For example, – (5, 19), (13, 1), (13, 24), and (15, 0) all have higher priority than (15, 7)Abstract Priority Queues 7 7.1.4 Process Priority in Unix This is the scheme used by Unix, e.g., nice +15 ./a.out reduces the priority of the execution of the routine a.out by 15 This allows the processor to be used by interactive programs – This does not significantly affect the runtime of CPUbound processesAbstract Priority Queues 8 7.1.4 Process Priority in Windows The priority of processes in Windows may be set in the Windows Task ManagerAbstract Priority Queues 9 7.1.5 Implementations Our goal is to make the run time of each operation as close to Q(1) as possible We will look at two implementations using data structures we already know: – Multiple queues—one for each priority – An AVL tree The next topic will be a more appropriate data structure: the heapAbstract Priority Queues 10 7.1.5.1 Multiple Queues Assume there is a fixed number of priorities, say M – Create an array of M queues – Push a new object onto the queue corresponding to the priority – Top and pop find the first empty queue with highest priorityAbstract Priority Queues 11 7.1.5.1 Multiple Queues template typename Type, int M class Multiqueue private: queueType queuearrayM; int queuesize; public: Multiqueue(); bool empty() const; Type top() const; void push( Type const , int ); Type pop(); ; template typename Type, int M MultiqueueType::Multiqueue(): queuesize( 0 ) // The compiler allocates memory for the M queues // and calls the constructor on each of them template typename Type, int M bool MultiqueueType::empty() const return ( queuesize == 0 ); Abstract Priority Queues 12 7.1.5.1 Multiple Queues template typename Type, int M void MultiqueueType::push( Type const obj, int pri ) if ( pri 0 pri = M ) throw illegalargument(); template typename Type, int M Type MultiqueueType::pop() queuearraypri.push( obj ); for ( int pri = 0; pri M; ++pri ) ++queuesize; if ( queuearraypri.empty() ) queuesize; return queuearraypri.pop(); template typename Type, int M Type MultiqueueType::top() const for ( int pri = 0; pri M; ++pri ) if ( queuearraypri.empty() ) // The priority queue is empty return queuearraypri.front(); throw underflow(); // The priority queue is empty throw underflow(); Abstract Priority Queues 13 7.1.5.1 Multiple Queues The run times are reasonable: – Push is Q(1) – Top and pop are both O(M) Unfortunately: – It restricts the range of priorities – The memory requirement is Q(M + n)Abstract Priority Queues 14 7.1.5.2 AVL Trees We could simply insert the objects into an AVL tree where the order is given by the stated priority: – Insertion is Q(ln(n)) void insert( Type const ); – Top is Q(ln(n)) Type front(); – Remove is Q(ln(n)) bool remove( front() ); There is significant overhead for maintaining both the tree and the corresponding balanceAbstract Priority Queues 15 7.1.5.3 Heaps Can we do better – That is, can we reduce some (or all) of the operations down to Q(1) The next topic defines a heap – A tree with the top object at the root – We will look at binary heaps – Numerous other heaps exists: • dary heaps • Leftist heaps • Skew heaps • Binomial heaps • Fibonacci heaps • Biparental heapsAbstract Priority Queues 16 Summary This topic: – Introduced priority queues – Considered two obvious implementations: • Arrays of queues • AVL trees – Discussed the run times and claimed that a variation of a tree, a heap, can do betterAbstract Priority Queues 17 References Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, The MIT Press, 2001, §6.5, pp.13844. Mark A. Weiss, rd Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, 2006, Ch.6, p.213. Joh Kleinberg and Eva Tardos, Algorithm Design, Pearson, 2006, §2.5, pp.5765. Elliot B. Koffman and Paul A.T. Wolfgang, Objects, Abstractions, Data Structures and Design using C++, Wiley, 2006, §8.5, pp.48996 These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W.Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017