## Saturday, January 2, 2016

### In-place Heap Sort

http://www.csl.mtu.edu/cs2321/www/newLectures/09_Inplace_Heap_Sort.html
Instead of building a separate data structure for the heap, we could use the same array for the inS and the heap while building the heap.  When inS is empty and we shrink the heap to build the output sequence, outS, the same array would contain both heap and outS.  As example let consider that the heap is always on the left side (lower index) of the array while inS and outS are kept to right (higher index). We need to keep track of the location of the division between the heap and sequence.  This is easy—it can be size of the heap.
To get a sequence in ascending order, we will use a Maximum heap instead of a Minimum heap: removeMin should removeMax. In other words we will build a heap with the maximum integer on top (at the root).
Example: Note indicates the division between heap and in/outS
input: |4 7 2 1 3
Remove from sequence and place in heap:
heap inS
4|7 2 1 3
7 4|2 1 3
7 4 2|1 3
7 4 2 1|3
7 4 2 1 3|
Remove max from heap and place in output sequence:
heap outS
4 2 3 1|7
3 2 1|4 7
2 1|3 4 7
1|2 3 4 7
Output: 1 2 3 4 7|
Note some addition to detail is required to keep the sorting O(n lg n). We must make sure that the method of inS and outS are O(1) and not O(n).  If the sequence methods are O(n) then the sorting complexity is O(n2).  In the above example:
• "remove element from inS" should use inS.removeFirst()
• "append element to outS" should use outS.insertFirst(integer)
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-sort2.html
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Java
```public static void heapSort(int[] a){
int count = a.length;

//first place a in max-heap order
heapify(a, count);

int end = count - 1;
while(end > 0){
//swap the root(maximum value) of the heap with the
//last element of the heap
int tmp = a[end];
a[end] = a[0];
a[0] = tmp;
//put the heap back in max-heap order
siftDown(a, 0, end - 1);
//decrement the size of the heap so that the previous
//max value will stay in its proper place
end--;
}
}

public static void heapify(int[] a, int count){
//start is assigned the index in a of the last parent node
int start = (count - 2) / 2; //binary heap

while(start >= 0){
//sift down the node at index start to the proper place
//such that all nodes below the start index are in heap
//order
siftDown(a, start, count - 1);
start--;
}
//after sifting down the root all nodes/elements are in heap order
}

public static void siftDown(int[] a, int start, int end){
//end represents the limit of how far down the heap to sift
int root = start;

while((root * 2 + 1) <= end){      //While the root has at least one child
int child = root * 2 + 1;           //root*2+1 points to the left child
//if the child has a sibling and the child's value is less than its sibling's...
if(child + 1 <= end && a[child] < a[child + 1])
child = child + 1;           //... then point to the right child instead
if(a[root] < a[child]){     //out of max-heap order
int tmp = a[root];
a[root] = a[child];
a[child] = tmp;
root = child;                //repeat to continue sifting down the child now
}else
return;
}
}```
https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Heapsort#Java_2
```public static void heapSort(int[] array) {
/* This method performs an in-place heapsort. Starting
* from the beginning of the array, the array is swapped
* into a binary max heap.  Then elements are removed
* from the heap, and added to the front of the sorted
* section of the array. */

/* Insertion onto heap */
for (int heapsize=0; heapsize<array.length; heapsize++) {
/* Step one in adding an element to the heap in the
* place that element at the end of the heap array-
* in this case, the element is already there. */
int n = heapsize; // the index of the inserted int
while (n > 0) { // until we reach the root of the heap
int p = (n-1)/2; // the index of the parent of n
if (array[n] > array[p]) { // child is larger than parent
arraySwap(array, n, p); // swap child with parent
n = p; // check parent
}
else // parent is larger than child
break; // all is good in the heap
}
}

/* Removal from heap */
for (int heapsize=array.length; heapsize>0;) {
arraySwap(array, 0, --heapsize); // swap root with the last heap element
int n = 0; // index of the element being moved down the tree
while (true) {
int left = (n*2)+1;
if (left >= heapsize) // node has no left child
break; // reached the bottom; heap is heapified
int right = left+1;
if (right >= heapsize) { // node has a left child, but no right child
if (array[left] > array[n]) // if left child is greater than node
arraySwap(array, left, n); // swap left child with node
break; // heap is heapified
}
if (array[left] > array[n]) { // (left > n)
if (array[left] > array[right]) { // (left > right) & (left > n)
arraySwap(array, left, n);
n = left; continue; // continue recursion on left child
} else { // (right > left > n)
arraySwap(array, right, n);
n = right; continue; // continue recursion on right child
}
} else { // (n > left)
if (array[right] > array[n]) { // (right > n > left)
arraySwap(array, right, n);
n = right; continue; // continue recursion on right child
} else { // (n > left) & (n > right)
break; // node is greater than both children, so it's heapified
}
}
}
}
}
}
}```