tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 9.2 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of heap. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Heaps 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Heaps 2 5 6 9 © 2014 Goodrich, Tamassia, Goldwasser 7 Heaps 1 Recall Priority Queue ADT q   q   q   A priority queue stores a collection of entries Each entry is a pair (key, value) Main methods of the Priority Queue ADT n   n   insert(k, v) inserts an entry with key k and value v removeMin() removes and returns the entry with smallest key © 2014 Goodrich, Tamassia, Goldwasser Heaps q   Additional methods n   n   q   min() returns, but does not remove, an entry with smallest key size(), isEmpty() Applications: n   n   n   Standby flyers Auctions Stock market 2 1 Heaps 3/19/14 Recall PQ Sorting q   We use a priority queue n   Insert the elements with a series of insert operations n   Remove the elements in sorted order with a series of removeMin operations q   The running time depends on the priority queue implementation: n   n   q   Algorithm PQ-Sort(S, C) Input sequence S, comparator C for the elements of S Output sequence S sorted in increasing order according to C P ← priority queue with comparator C while ¬ () e ← (S. first ()) (e, e) while ¬() e ← ().getKey() (e) Unsorted sequence gives selection-sort: O(n2) time Sorted sequence gives insertion-sort: O(n2) time Can we do better? © 2014 Goodrich, Tamassia, Goldwasser Heaps 3 Heaps q   q   q   A 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)) q   The last node of a heap is the rightmost node of maximum depth 2 Complete Binary Tree: let h be the height of the heap n   n   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 © 2014 Goodrich, .