Heap Sort
Quick Notes Heapsort’s running time is O( n lg n ). Like insertion sort, but unlike merge sort, heapsort sorts in place. Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a “heap,” to manage information. Heaps The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. An array A that represents a heap is an object with two attributes: A. length , which (as usual) gives the number of elements in the array, and A .heap-size , which represents how many elements in the heap are stored within array A. That is, although A[1 . . A. length ] may contain numbers, only the elements in A[1 . . A. heap-size ], where 0 ≤ A. heap-size ≤ A. length , are valid elements of the heap. The root ...