CSE 214 Lecture 35: HeapSort
Document Summary
Take one element at a time starting from the left side of an array and keep inserting it into a heap. We assume that the first element in the array is already a heap. We start sorting from the second element at index 1 until index n-1. Inserting is easier than removing from a heap since in removal, you must make sure that all values follow the convention of a heap such as parent to child relations. In a max heap, the parent must be greater than the child. Start position at 0 while (position*2 + 1 < heapsize) { childpos = position*2 + 1; if (childpos < heapsize-1 && data[childpos+1] > data[childpos]) childpos++; if (data[position]