L7 - Tree-based Sorting.pdf

CP312 Algorithm Design and Analysis I LECTURE 7: TREE-BASED SORTING 1 Sorting with Trees In precious lectures we saw how to sort using arrays. In this lecture, we will see the effect of changing data structures on the performance of an algorithm. In particular, we will use binary trees instead of ar...

CP312 Algorithm Design and Analysis I LECTURE 7: TREE-BASED SORTING 1 Sorting with Trees In precious lectures we saw how to sort using arrays. In this lecture, we will see the effect of changing data structures on the performance of an algorithm. In particular, we will use binary trees instead of arrays. 2 Binary Trees - Review Root 7 Node 𝒙 Key of node 𝒙 𝒙. 𝒌𝒆𝒚 10 6 𝒙. 𝒓𝒊𝒈𝒉𝒕 right child of node 𝒙 𝒙. 𝒍𝒆𝒇𝒕 Left child of node 𝒙 5 1 4 3 11 Height 𝒉=𝟑 8 3 Leaves 3 Binary Search Trees (BST) Key Property: BST is a binary tree data structure where for every node 𝑥 with left child 𝑦 and right child 𝑧: 𝑦. 𝑘𝑒𝑦 < 𝑥. 𝑘𝑒𝑦 < 𝑧. 𝑘𝑒𝑦 8 5 20 3 1 7 4 6 12 25 16 BST operations: 1.) BST-search(𝑘) 2.) BST-insert(𝑘) 3.) BST-delete(𝑘) 4 Binary Search Trees (BST) 8 5 20 Maximum 3 7 12 25 Minimum 1 4 6 Successor of 𝟓 16 Predecessor of 𝟓 5 Binary Search Trees (BST) BST-Search(𝑘) 8 𝑘=6 5 20 3 1 7 4 6 12 25 16 6 Binary Search Trees (BST) 8 𝑘=6 5 7 4 20 𝑘5 3 1 20 4 7 6 12 25 16 8 Binary Search Trees (BST) BST-Search(𝑘) 8 𝑘=6 5 20 3 7 12 25 𝑘8 3 1 7 4 20 6 12 25 16 12 Binary Search Trees (BST) BST-Insert(𝑘) 8 11 5 20 3 1 7 4 6 12 𝑘 < 20 25 16 13 Binary Search Trees (BST) BST-Insert(𝑘) 8 11 5 20 3 7 12 25 𝑘 < 12 1 4 6 16 14 Binary Search Trees (BST) BST-Insert(𝑘) 𝑇 𝑛 =𝑂 ℎ 8 5 20 3 1 7 4 6 12 11 25 16 Worst-case 𝑇 𝑛 =Θ 𝑛 15 Binary Search Trees (BST) BST-delete(𝑘) 8 6 𝑘 is a leaf 1. BST-search(𝑘) 2. Delete node 𝑘 5 3 1 7 4 6 20 12 25 16 16 Binary Search Trees (BST) BST-delete(𝑘) 8 6 𝑘 is a leaf 1. BST-search(𝑘) 2. Delete node 𝑘 5 3 1 7 4 20 12 25 16 17 Binary Search Trees (BST) BST-delete(𝑘) 8 3 𝑘 is a sub-tree and successor has no children 1. BST-search(𝑘) 2. Replace 𝑘 with successor 3. Delete node 𝑘 5 3 1 7 4 6 20 12 25 16 18 Binary Search Trees (BST) BST-delete(𝑘) 8 3 𝑘 is a sub-tree and successor has no children 1. BST-search(𝑘) 2. Replace 𝑘 with successor 3. Delete node 𝑘 5 4 1 7 3 6 20 12 25 16 19 Binary Search Trees (BST) BST-delete(𝑘) 8 3 𝑘 is a sub-tree and successor has no children 1. BST-search(𝑘) 2. Replace 𝑘 with successor 3. Delete node 𝑘 5 4 1 7 3 6 20 12 25 16 20 Binary Search Trees (BST) BST-delete(𝑘) 8 3 𝑘 is a sub-tree and successor has no children 1. BST-search(𝑘) 2. Replace 𝑘 with successor 3. Delete node 𝑘 5 4 1 7 6 20 12 25 16 21 Binary Search Trees (BST) There are more cases, but you can try to see how they work on your own. BST-delete(𝑘) 𝑇 𝑛 =𝑂 ℎ 8 5 20 4 1 7 6 12 25 16 Worst-case 𝑇 𝑛 =Θ 𝑛 22 Binary Search Trees (BST) In-Order Traversal 8 10 4 7 InorderWalk(root) 5 InorderWalk 𝑥 : 𝐢𝐟 𝑥 ≠ NULL InorderWalk(𝑥. 𝑙𝑒𝑓𝑡) print(𝑥. 𝑘𝑒𝑦) InorderWalk(𝑥. 𝑟𝑖𝑔ℎ𝑡) 20 𝑇 𝑛 =𝑂 𝑛 2 6 3 7 3 1 1 4 8 12 25 11 5 6 9 16 23 Assuming Tree is Balanced! BST Sort 𝐴 𝑇 𝑛 = Θ 𝑛 lg 𝑛 + Θ 𝑛 = Θ 𝑛 lg 𝑛 2 8 7 1 3 5 6 4 Create BST (𝑛 BST-inserts) Θ 𝑛 lg 𝑛 In-order Traversal Θ 𝑛 1 2 3 4 5 6 7 8 24 BST Sort In order to make sure that the tree is balanced, we can use various other tree-based data structures: ◦ ◦ ◦ ◦ ◦ ◦ Red-black Trees AVL Trees (better than RB-trees for search-intensive applications) Splay Trees (pushes frequently accessed elements closer to the root; useful for caching) Treap (a combination of a tree and a heap) B-Trees (for large multi-degree data) 2-3 / 2-3-4 trees (special cases of B-trees) But on average, randomly inserting elements in a standard BST gives 𝑂(𝑛 lg 𝑛) 25 Heapsort: At a glance Worst-case 𝑂(𝑛 lg 𝑛) - like merge-sort, but unlike insertion sort Sorts in place – like insertion, but unlike merge-sort Heapsort combines the best attributes of these deterministic sorting algorithms. 26 Binary Max-Heap Key Property: Max-Heap a binary tree data structure where for every node 𝑥: Parent 𝑥. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦 16 Maximum 15 10 8 2 7 4 1 9 3 Max-Heap operations: 1.) HEAPIFY(𝑖) 2.) HEAP-getmax 3.) HEAP-insert(𝑘) 27 Binary Max-Heap 1 Key Property: Max-Heap a binary tree data structure where for every node 𝑥: Parent 𝑥. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦 16 2 3 Array Representation: Children of Node 𝑖 at indices 2𝑖 and 2𝑖 + 1 15 4 5 8 7 8 9 2 4 6 7 9 10 1 10 𝐴 3 1 2 3 4 5 6 7 8 9 10 16 15 10 8 7 9 3 2 4 1 𝐴 1, … , ℎ𝑒𝑎𝑝𝑠𝑖𝑧𝑒 28 Binary Max-Heap 1 Key Property: Max-Heap a binary tree data structure where for every node 𝑥: Parent 𝑥. 𝑘𝑒𝑦 ≥ 𝑥. 𝑘𝑒𝑦 16 2 3 Array Representation: Children of Node 𝑖 at indices 2𝑖 and 2𝑖 + 1 15 4 6 5 8 7 8 9 2 10 4 9 10 1 7 𝐴 Number of leaves in a heap is 𝑛/2 3 1 2 3 4 5 6 7 8 9 10 16 15 10 8 7 9 3 2 4 1 𝐴 1, … , ℎ𝑒𝑎𝑝𝑠𝑖𝑧𝑒 29 Max-Heap HEAPIFY(𝑖) 15 is largest child 16 Move node 𝑖 down the tree until the heap property is satisfied. 𝑖 4 10 15 2 7 8 9 3 1 30 Max-Heap HEAPIFY(𝑖) 16 8 is largest child 15 10 𝑖 4 2 7 8 9 3 1 31 Max-Heap HEAPIFY(𝑖) 16 15 10 8 7 9 3 𝑖 2 4 1 32 Max-Heap HEAPIFY(𝑖) 𝑇 𝑛 = 𝑂 ℎ = 𝑂 lg 𝑛 16 15 10 8 2 7 4 9 3 1 33 Max-Heap HEAP-getmax 16 15 10 8 2 7 4 1 9 3 Exchange with last node in heap 34 Max-Heap HEAP-getmax 1 15 10 8 2 7 4 16 9 3 Retrieve maximum 35 Max-Heap HEAP-getmax 1 15 8 2 10 7 4 9 3 Retrieve maximum 36 Max-Heap Call HEAPIFY(1) HEAP-getmax 1 15 8 2 10 7 9 3 4 37 Max-Heap Call HEAPIFY(1) HEAP-getmax 15 1 8 2 10 7 9 3 4 38 Max-Heap Call HEAPIFY(1) HEAP-getmax 15 8 1 2 10 7 9 3 4 39 Max-Heap Call HEAPIFY(1) HEAP-getmax 15 8 4 2 10 7 9 3 1 40 Max-Heap 15 Exchange 𝐴 with last node then call HEAPIFY(1) 8 4 2 HEAP-getmax 𝑇 𝑛 = 𝑂 lg 𝑛 10 7 9 3 1 41 Max-Heap 1 HEAP-insert(𝑘) 15 2 3 8 10 4 5 4 7 8 6 1 7 9 9 2 11 𝐴 3 1 2 3 4 5 6 7 8 9 15 8 10 4 7 9 3 2 1 42 Max-Heap 1 HEAP-insert(𝑘) 15 2 3 8 10 4 5 4 7 8 1 11 7 9 10 9 2 6 𝐴 3 1 2 3 4 5 6 7 8 9 10 15 8 10 4 7 9 3 2 1 11 43 Max-Heap 1 HEAP-insert(𝑘) 15 2 3 8 10 4 5 4 7 8 1 11 7 9 10 9 2 6 𝐴 3 1 2 3 4 5 6 7 8 9 10 15 8 10 4 7 9 3 2 1 11 44 Max-Heap 1 HEAP-insert(𝑘) 15 2 3 8 10 4 5 4 11 8 1 7 7 9 10 9 2 6 𝐴 3 1 2 3 4 5 6 7 8 9 10 15 8 10 4 11 9 3 2 1 7 45 Max-Heap 1 HEAP-insert(𝑘) 15 2 3 11 10 4 5 4 8 8 1 7 7 9 10 9 2 6 𝐴 3 1 2 3 4 5 6 7 8 9 10 15 11 10 4 8 9 3 2 1 7 46 Max-Heap 1 HEAP-insert(𝑘) 15 𝑇 𝑛 = 𝑂 lg 𝑛 2 3 11 10 4 5 4 8 8 1 7 7 9 10 9 2 6 𝐴 3 1 2 3 4 5 6 7 8 9 10 15 11 10 4 8 9 3 2 1 7 47 Heapsort 𝐴 2 𝑇 𝑛 = Θ 𝑛 lg 𝑛 8 7 1 3 5 6 4 𝑛 HEAP-insert Θ 𝑛 lg 𝑛 𝑛 HEAP-getmax Θ 𝑛 lg 𝑛 1 2 3 4 5 6 7 8 Reverse Order Θ(𝑛) 48 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 3 10 4 5 8 2 8 16 1 7 6 10 9 12 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 3 10 8 2 6 5 12 16 1 49 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 3 10 4 5 8 2 8 16 1 7 6 10 9 12 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 3 10 8 2 6 5 12 16 1 50 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 3 10 4 5 8 2 8 16 1 7 6 10 9 12 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 3 10 8 2 6 5 12 16 1 51 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 3 10 4 5 16 2 8 8 1 7 6 10 9 12 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 3 10 16 2 6 5 12 8 1 52 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 3 10 4 5 16 2 8 8 1 7 6 10 9 12 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 3 10 16 2 6 5 12 8 1 53 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 7 2 3 16 10 4 5 12 2 8 8 1 7 6 10 9 3 6 𝐴 5 1 2 3 4 5 6 7 8 9 10 7 16 10 12 2 6 5 3 8 1 54 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 16 2 3 12 10 4 5 8 2 8 7 6 1 7 6 10 9 3 Looks like T 𝑛 = 𝑂(𝑛 lg 𝑛) But we can do a better analysis 𝐴 5 1 2 3 4 5 6 7 8 9 10 16 12 10 8 2 6 5 3 7 1 55 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 16 2 3 12 10 4 5 8 2 8 10 9 3 7 1 6 6 7 5 Time to HEAPIFY 𝑖 = 𝑂(height of subtree rooted at 𝑖) 𝑛 𝑛 𝑛 𝑛 𝑇 𝑛 = 𝑂 0 + 2 𝑂 1 + 3 𝑂 2 + ⋯ + lg 𝑛+1 𝑂(lg 𝑛) 2 2 2 2 56 Max-Heap BUILD-HEAP(𝐴) 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 16 2 3 12 10 4 5 8 2 8 10 9 6 6 7 1 5 Time to HEAPIFY 𝑖 = 𝑂(height of subtree rooted at 𝑖) lg 𝑛 3 7 𝑇 𝑛 =෍ 𝑖=0 𝑛 2𝑖+1 lg 𝑛 𝑖 𝑂 𝑖 = 𝑂 𝑛෍ 𝑖 2 𝑖=0 57 𝑘 σ∞ 𝑘𝑥 𝑖=1 1 Max-Heap ≤ 𝑥 1−𝑥 2 for 𝑥 < 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 16 2 3 12 10 4 5 8 2 8 10 9 6 7 1 7 6 5 Time to HEAPIFY 𝑖 = 𝑂(height of subtree rooted at 𝑖) lg 𝑛 3 BUILD-HEAP(𝐴) 𝑇 𝑛 =෍ 𝑖=0 𝑛 2𝑖+1 lg 𝑛 𝑖 𝑂 𝑖 = 𝑂 𝑛෍ 𝑖 2 𝑖=0 58 𝑘 σ∞ 𝑘𝑥 𝑖=1 1 Max-Heap ≤ 𝑥 1−𝑥 2 for 𝑥 < 1 for 𝑖 = 𝑛/2 down to 1 HEAPIFY(𝑖) 16 2 3 12 10 4 5 8 2 8 10 9 6 7 1 7 6 5 Time to HEAPIFY 𝑖 = 𝑂(height of subtree rooted at 𝑖) lg 𝑛 3 BUILD-HEAP(𝐴) 𝑇 𝑛 =෍ 𝑖=0 𝑛 2𝑖+1 lg 𝑛 𝑖 𝑂 𝑖 = 𝑂 𝑛෍ 𝑖 2 = 𝑂(𝑛) 𝑖=0 59 Heapsort 𝐴 2 𝑇 𝑛 = Θ 𝑛 lg 𝑛 8 7 1 3 5 6 4 BUILD-HEAP(𝐴) 𝑂(𝑛) 𝑛 HEAP-getmax Θ 𝑛 lg 𝑛 1 2 3 4 5 6 7 8 Reverse Order Θ(𝑛) 60