Report

1 Priority Queue Erick, Eka, Reddy © Sekolah Tinggi Teknik Surabaya » Priority Queue ADT + Keys, Priorities, and Total order Relations + Sorting with a Priority Queue » Priority Queue implementation + Implementation with an unsorted sequence + Implementation with a sorted sequence 2 © Sekolah Tinggi Teknik Surabaya » A priority queue stores a » Additional methods collection of entries / ˃ min() returns, but does not node remove, an node with » Each node is a pair smallest key (key, value) ˃ size(), isEmpty() » Main methods of the Priority Queue ADT ˃ insert(k, x) » inserts an node with key k and value x ˃ removeMin() removes and returns the node with smallest key © Sekolah Tinggi Teknik Surabaya Applications: ˃ Standby flyers ˃ Auctions ˃ Stock market 3 » Suppose that you have a few assignments from different courses. Which assignment will you want to work on first? Course Database Systems Introduction to C++ Data Structure & Algorithm Structured Systems Analysis Priority 2 4 1 3 Due day October 3 October 10 September 29 October 7 » You set your priority based on due days. Due days are called keys. © Sekolah Tinggi Teknik Surabaya 4 Student Name Bill Scott Bob Jones Alan Smith Susan Kane Student Number 110102 110140 110243 110176 Final Score 65 76 86 80 » Any of the attributes, Student Name, Student Number, or Final Score can be used as keys. » Note: Keys may not be unique (Final Score). © Sekolah Tinggi Teknik Surabaya 5 Brand Motormaster Goodyear Michelin Price $61.49 $98.99 $101.99 Warranty (km) 110,000 220,000 150,000 » Suppose we are looking for tires for a passenger car. How can we weight the tires so we can select the tires? » The key may consist of not only one attribute such as price. In fact, we want to consider factors such as brands and warranty as well. » So the key may be more complex than just one value. © Sekolah Tinggi Teknik Surabaya 6 » Keys in a priority » Mathematical concept queue can be of total order relation ˃ Reflexive property: arbitrary objects on xx which an order is ˃ Antisymmetric property: defined xyyxx=y » Two distinct entries in ˃ Transitive property: xyyzxz a priority queue can have the same key 7 © Sekolah Tinggi Teknik Surabaya » Not everything can have a total order relation. » Non-example: » For 2-D vectors v1 = (x1, x2) and v2 = (x3, x4), define the following ordering rule: » v1 v2 if x2 - x1 == x4 - x3 » Then we have » 4-1=7-4 » Therefore, (1, 4) (4, 7) and (4, 7) (1, 4). » But (1,4) (7, 4), namely, the relation does not satisfy the » antisymmetric property. © Sekolah Tinggi Teknik Surabaya 8 » If a comparison rule defines a total order relation, it will never lead to a comparison contradiction. » the smallest key: If we have a finite number of elements with a total order relation, then the smallest key, denoted by kmin, is well-defined: kmin is the key that satisfies kmin k for any other key k. » Being able to find the smallest key is very important because in many cases, we want to have the element with the smallest key. © Sekolah Tinggi Teknik Surabaya 9 » priority queue: A container of elements, each having an associated key that is provided at the time the element is inserted. » The two fundamental methods of a priority queue P: insertItem(k,e): Insert an element e with key k into P. removeMin(): Return and remove from P an element with the smallest key. © Sekolah Tinggi Teknik Surabaya 10 » We can use a priority queue to sort a set of comparable elements » Algorithm PQ-Sort(S, C) Input sequence S, comparator C for the elements of S Output sequence S sorted in 1. Insert the elements one increasing order according to C by one with a series of P priority queue with insert operations comparator C 2. Remove the elements while not S.isEmpty () in sorted order with a e S.removeFirst () series of removeMin P.insert (e, 0) operations while not P.isEmpty() e P.removeMin().key() The running time of S.insertLast(e) this sorting method depends on the priority queue implementation © Sekolah Tinggi Teknik Surabaya 11 » We have a sequence S with 6 integers (elements). Also we have an empty priority queue P. S 4 0 7 8 2 1 P » While S is not empty insert to P © Sekolah Tinggi Teknik Surabaya 12 » After the first step, all the elements are now in the priority queue, with themselves as keys. S P 0,0 1,1 2,2 4,4 7,7 8,8 13 © Sekolah Tinggi Teknik Surabaya » The first three elements have been extracted from P and inserted into S in order. The element with the smallest key in P now is 4,4, which will be extracted next time. S 0 1 2 4,4 7,7 P © Sekolah Tinggi Teknik Surabaya 8,8 14 » After the second step: Now the elements are sorted in S. S 0 1 2 4 7 8 P 15 © Sekolah Tinggi Teknik Surabaya » The priority queue abstract data type supports the following methods: size(): Return the number of elements in P. Input: None; Output: Integer isEmpty(): Test whether P is empty. Input: None; Output: Boolean inserItem(k,e): Insert a new element e with key k into P. Input: Objects k (key) and e (element); Output: None minElement(): Return (but do not remove) an element of P with the smallest key; an error condition occurs if the priority queue is empty. Input: None; Output: Object (element) minKey(): Return a smallest key in P; an error condition occurs if the priority queue is empty. Input: None; Output: Object (key) removeMin(): Remove from P and return an element with the smallest key; an error condition occurs if the priority queue is empty. Input: None; Output: Object (element) © Sekolah Tinggi Teknik Surabaya 16 » The following table shows a series of operations and their effects on an initially empty priority queue P. Operation insertItem(5,A) insertItem(9,C) insertItem(3,B) insertItem(7,D) minElement() minKey() removeMin() size() removeMin() removeMin() removeMin() removeMin() isEmpty() © Sekolah Tinggi Teknik Surabaya Output B 3 B 3 A D C “error” true Priority Queue {(5,A)} {(5,A),(9,C)} {(3,B),(5,A),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(5,A),(7,D),(9,C)} {(5,A),(7,D),(9,C)} {(7,D),(9,C)} {(9,C)} {} {} {} 17 » Node Class » Icomparable ADT 18 © Sekolah Tinggi Teknik Surabaya » A node in a priority queue is simply a keyvalue pair » Priority queues store nodes to allow for efficient insertion and removal based on keys » Methods: ˃ key(): returns the key for this node ˃ value(): returns the value associated with this node © Sekolah Tinggi Teknik Surabaya » As C# class: public class Node { public int key; public T value; } 19 » A comparator encapsulates the action of comparing two objects according to a » The primary method of given total order relation the Comparator ADT: » A generic priority queue ˃ compare(x, y): Returns uses an auxiliary an integer i such that i < 0 if a < b, i = 0 if a = b, comparator and i > 0 if a > b; an error » The comparator is external occurs if a and b cannot to the keys being compared be compared. » When the priority queue needs to compare two keys, it uses its comparator 20 © Sekolah Tinggi Teknik Surabaya » Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an unsorted sequence, we use the method insertLast(p) of S to implement insertItem(k,e) of the priority queue P. » To perform operations including minElement, minKey, and removeMin, we have to inspect all the elements of the sequence S to find the element with the smallest key. © Sekolah Tinggi Teknik Surabaya 21 » Assume we have the elements stored in an unsorted sequence show here. » To perform the removeMin() operation, we have to inspect all elements to find the element (0,0) that has the smallest key. P 1,1 4,4 0,0 2,2 7,7 8,8 22 © Sekolah Tinggi Teknik Surabaya » Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an sorted sequence, we can easily extract the element with the smallest key with the combination of methods remove() and first() of S. » However, to perform operation insertItem, we need to scan through the sequence S to find the apropriate position to insert the new element and key. © Sekolah Tinggi Teknik Surabaya 23 » To insert the pair (6,6), we have to scan through the sequence until we find the right place (between (4,4) and (7,7)). P 0,0 1,1 2,2 4,4 7,7 8,8 6,6 24 © Sekolah Tinggi Teknik Surabaya » Assume that the size of the sequence is n. Method Unsorted S Sorted S size, isEmpty fast fast O(n) insertItem fast minElement, minKey, removeMin O(n) fast 25 © Sekolah Tinggi Teknik Surabaya Inheritance • Use in the small, when a derived class "is-a" base class – enables code reuse – enables design reuse & polymorphic programming • Example: – a Student is-a Person Person Student Undergraduate Microsoft Employee Graduate Staff Faculty 26 Implementation • C# supports single inheritance – public inheritance only (C++ parlance) – base keyword gives you access to base class's members Person public class Student : Person { private int m_ID; public Student(string name, int age, int id) :base(name, age) { this.m_ID = id; } Student // constructor } Microsoft 27 Binding • C# supports both static and dynamic binding – determined by absence or presence of virtual keyword – derived class must acknowledge with new or override public class Person { . . . // statically-bound public string HomeAddress() { … } public class Student : Person { . . . // dynamically-bound public virtual decimal Salary() { … } public new string HomeAddress() { … } } public override decimal Salary() { … } } Microsoft 28 All classes inherit from System.Object System-defined types Object User-defined types String Array Primitive types Microsoft Boolean Single Byte Double Int16 Decimal Int32 DateTime Int64 TimeSpan Char Guid ValueType Exception Delegate Class1 Enum Structure1 Multicast Delegate Class2 Delegate1 Class3 Enum1 29 Part 4 • Interfaces… Microsoft 30 Interfaces • An interface represents a design • Example: – the design of an object for iterating across a data structure – interface = method signatures only, no implementation details! – this is how foreach loop works… public interface IEnumerator { void Reset(); // reset iterator to beginning bool MoveNext(); // advance to next element object Current { get; } // retrieve current element } Microsoft 31 Why use interfaces? • Formalize system design before implementation – especially helpful for PITL (programming in the large) • Design by contract – interface represents contract between client and object • Decoupling – interface specifies interaction between class A and B – by decoupling A from B, A can easily interact with C, D, … Microsoft 32 .NET is heavily influenced by interfaces • • • • • • • • IComparable ICloneable IDisposable IEnumerable & IEnumerator IList ISerializable IDBConnection, IDBCommand, IDataReader etc. Microsoft 33 Example • Sorting – FCL contains methods that sort for you – sort any kind of object – object must implement IComparable object[] students; students = new object[n]; students[0] = new Student(…); students[1] = new Student(…); . . . public interface IComparable { int CompareTo(object obj); } Array.Sort(students); Microsoft 34 To be a sortable object… • Sortable objects must implement IComparable • Example: – Student objects sort by id base class interface public class Student : Person, IComparable { private int m_ID; . . . Person Student int IComparable.CompareTo(Object obj) { Student other; other = (Student) obj; return this.m_ID – other.m_ID; } } Microsoft 35 Summary • Object-oriented programming is *the* paradigm of .NET • C# is a fully object-oriented programming language – fields, properties, indexers, methods, constructors – garbage collection – single inheritance – interfaces • Inheritance? – consider when class A "is-a" class B – but you only get single-inheritance, so make it count • Interfaces? – consider when class C interacts with classes D, E, F, … – a class can implement any number of interfaces Microsoft 36