Using Heap Sort to partially sort arrays.

The Heap mimics a binary tree, but is actually as an array.

To get the first k items from an array of n items, we establish the first k positions in the array as a heap.

We first convert the first k elements into a heap (which is faster than adding them one at a time).  Then for the rest of the array, we see if the element we're looking at comes after the top of the heap in sorted order.  (If it does, it couldn't possibly be one of the first k elements.)  If it does comes before the top of the heap in sorted order, then the top of the heap could not be one of the first k elements, so it is removed from the heap and the current element is added to the heap.

Then the first k elements are removed from the heap which also puts them in order since heap elements are always removed in reverse sorted order.

You end up with an array with first k elements correct and the rest of the elements an unsorted mishmash.  But this much faster than sorting the whole array.

Adding to the heap:

The heap is in reality an array.  If the heap is currently of size hsz, then adding to heap means I take the element A[hsz] and add this element specifically to the heap, meaning the heap is now of size hsz+1.  This is accomplished by comparing the node to its parent in the heap and swapping it with its parent if it is larger than its parent, and continuing to do this until the new node is smaller than its parent or is at the top of the heap.

Removing the heap:  The heap is size hsz.  We know that A[0] is the largest element in the heap (top of the heap).  So, we swap this element with A[hsz-1], and record the new heap size as hsz-1.  This means that A[hsz-1] is no longer in the heap.

To extract a sorted array from a heap (a heap can be thought as partially sorted but not completely), just keep extracting the top element.  This will spit out all the elements of the heap in reverse sorted order, so you just load the array backwards.

QuickSelect:

The idea behind QuickSelect is that you are looking for the kth element in sorted order without sorting the whole array.  (I have 10000 elements in my array and I want to find the 3721st. (in sorted order) without sorting the whole array.)

Never use these sorts:  Bubble Sort, Selection Sort, Insertion Sort.

QuickSelect is a modified version of QuickSort.  Find a random pivot.  Move everything around in the array so that the pivot is in the right place...just like in QuickSort.  Since the pivot is in the right place, you know where it is.  So, say you're looking for the 3721st. element and the pivot you randomly selected is in position 6057.  Then the 3721st. has to come before the pivot, so it's not in that part of the array that comes after the pivot.
                 v
 0 1 2 3 4 5 6 7 8 9
 Q E R P I O T U W Y   We want to find element 7.  It's U.
               ^