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
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Java
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: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:
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|
- "remove element from inS" should use inS.removeFirst()
- "append element to outS" should use outS.insertFirst(integer)
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 } } } } } } }
