CSC263H1 Lecture Notes - Lecture 4: Binary Tree, Heapsort
Document Summary
Once the items are in an array (in any order) we can consider them a heap that has the corsdrect shape and then we have to x the order - o(n) heapify(a,i) Because each item in the second half of the array is already a heap (it"s a leaf), the preconditions for heapify are always met before each call. Trace build-heap on input a = [1, 5, 7, 6, 2, 9, 4, 8]: We make o(n) calls to heapify and each takes o(log n) time, so we immidiately get a bound of o(n log n). But we can do better by analyzing more carefully. The running time of each call to heapify is proportional to the height of the tree on which it is called. So we get that the total time taken is (cid:32)log n(cid:88) O (cid:33) h a where a = # of subtrees of height h. A complete tree with n nodes contains at most(cid:6) n.
