Heapsort.md (1162B)
1 +++ 2 title = "Heapsort" 3 +++ 4 5 # Heapsort 6 7 Intuition: 8 9 - input array is a max-heap (‘neat binary tree’) 10 - largest element is at the top 11 - deal with height of the tree (logn) 12 - have to maintain max-heap property 13 14 Tree definitions: 15 16 - depth: length of the pat to root from a node 17 - height: max path to a leaf 18 - binary: every node has 0, 1, or 2 successors 19 - almost complete if filled left-to-right 20 - an almost complete binary tree corresponds to an array 21 - height = floor(logn) 22 - parent = index/2 23 - left = index × 2 24 - right = (index × 2)+1 25 26 Heap: 27 28 - almsot complete binary tree, labelled with key from totally ordered set 29 - when walking downward, keys decrease 30 - hence largest key is at the top 31 - to reconstruct max-heap, bubble elements down and left — maxHeapify 32 - O(logn) 33 - building: bottom-up, from lowest level (which is already heaps) — buildMaxHeap 34 - O(n) 35 36 Heapsort: 37 38 - algorithm: 39 - first: turn input-array into max-heap 40 - loop: 41 - swap root key with last node key 42 - exclude last node form heap (decrease heap size) 43 - reconstruct heap 44 - if sorted (heap size 0), exit 45 - in-place 46 - worst-case is O(nlogn)