Note that there are, in general, many possible downward paths – which one do we choose? 7 5 6 w 9.Algorithm downheap restores the heap-order property by swapping key k along a downward path from the root.After replacing the root key with the key k of the last node, the heap-order property may be violated.Restore the heap-order property 2 5 6 w 9 7 last node 7 5 6 w 9 new last node.Replace the root key with the key of the last node w.The removal algorithm consists of three steps.Method removeMinof the priority queue ADT corresponds to the removal of the root key from the heap.Since a heap has height O(logn), upheapruns in O(logn) time 2 1 5 1 5 2 9 7 6 9 7 6.Upheapterminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k.Algorithm upheaprestores the heap-order property by swapping k along an upward path from the insertion node.After the insertion of a new key k, the heap-order property may be violated.Method insert of the priority queue ADT involves inserting a new entry with key k into the heap The insertion algorithm consists of two steps Store the new entry at the next available location Restore the heap-order property Insertion into a Heap 2 5 6 z 9 7 new node 2 5 6 z 9 7 1 For simplicity, we will typically show only the keys in the pictures (2, Sue) (5, Pat) (6, Mark) (7, Anna) (9, Jeff).We keep track of the position of the last node.We store a (key, element) item at each internal node.We can use a heap to implement a priority queue.Thus, n ≥ 2h, i.e., h ≤ log n depth keys 0 1 1 2 h-1 2h-1 h 1.Since there are 2i keys at depth i=0, …, h- 1 and at least one key at depth h, we have n ≥ 1 + 2 + 4 + … + 2h-1 + 1.Let h be the height of a heap storing nkeys.Theorem: A heap storing nkeys has height O(logn) Proof: (we apply the complete binary tree property).We will assume min heaps.Ī min heap is a binary tree storing keys at its nodes and satisfying the following properties: Heap-order: for every internal node v other than the root key(v) ≥ key(parent(v)) (Almost) complete binary tree: let h be the height of the heap for i= 0, …, h- 1, there are 2i nodes of depth i at depth h– 1 the internal nodes are to the left of the external nodes Only the rightmost internal node may have a single child The last node of a heap is the rightmost node of depth h Min Heaps 2 5 6 9 7 Remember that O(logn) is almost as good as O(1)!.Implementation with an unsorted list Performance: inserttakes O(1) time since we can insert the item at the beginning or end of the sequence removeMinand mintake O(n) time since we have to traverse the entire sequence to find the smallest key Implementation with a sorted list Performance: inserttakes O(n) time since we have to find the right place to insert the item removeMinand mintake O(1) time, since the smallest key is at the beginning 4 5 2 3 1 1 2 3 4 5 Sequence-based Priority Queue Is this tradeoff inevitable? Keys in a priority queue can be arbitrary objects on which an order is defined Two distinct entries in a priority queue can have the same key Mathematical concept of total order relation ≤ Reflexive property:x≤x Antisymmetric property:x≤y∧y≤xx=y Transitive property:x≤y∧y≤zx≤z Total Order RelationsĪn entry in a priority queue is simply a key-value pair Methods: getKey(): returns the key for this entry getValue(): returns the value for this entry As a Java interface: /** * Interface for a key-value * pair entry **/ public interface Entry Example Comparator min() returns, but does not remove, an entry with smallest key.
removeMin() removes and returns the entry with smallest key.insert(k, x) inserts an entry with key k and value x.Main methods of the Priority Queue ADT.A priority queue stores a collection of entries.a comparator, passed to the constructor.Elements are prioritized based either on.The Java Collections Framework (Ordered Data Types) Iterable Interface Abstract Class Collection Class List Abstract Collection Queue Abstract List Abstract Queue Priority Queue Abstract Sequential List Vector Array List Stack Linked List
0 kommentar(er)
