
Heap sort is a tree selection sort method, which is characterized by: the sorting process, the array [0, ..., n1] as a complete binary tree sequential storage structure, the use of complete binary tree internal parent node and child relationship between nodes, choose keywords maximum (minimum) element in the current disorder in the area.
1. If array [0, ..., n1] represents a complete binary tree stored in the order mode, the inherent relationship between parent and child node pointer node pointer is as follows:
Any node pointer i: parent: i == 0 null:? (I1) / 2
Left Children: 2 * i + 1
Right Children: 2 * i + 2
2. The definition of the heap: n keyword sequence array [0, ..., n1], if and only if the following requirements are met: (0 < = i < = (n1) / 2)
1. array [i] < = array [2 * i + 1] and array [i] < = array [2 * i + 2]; root called small heap;
2. array [i]> = array [2 * i + 1] and array [i]> = array [2 * i + 2]; I called large root heap;
3. The establishment of large root heap:
Complete binary tree with n nodes array [0, ..., n1], the last node n1 is the first (n11) Children / 2 nodes. The first (n11) / 2 nodes to adjust the subtree root, so that the subtree called the heap.
For large root heap adjustment method is: If [root keyword] is less than [children around the greater keyword], then the switch.
After forward successively for each node ((n2) / 2  1) ~ 0 rooted subtrees adjustment to see if the node value is about greater than the value of the child node, if it is, the more the left and right child nodes Great value to exchange, could undermine the heap after switching to the next level, then continue using the above method to build the next level of the stack, the stack until the node to the root of the subtree constitution.
Repeated use of the above adjustments heap pile construction method until the root node.
4. heap sort :( large root heap)
. A will be stored in array [0, ..., n1] n elements in the completion of the initial heap;
. B element will be top of the heap and stack bottom element exchange, the maximum value of the sequence is already in the right place;
c. But this time the reactor was destroyed, the top of the heap element adjusted downward so that it continued to maintain a large root heap of nature, and then repeat step (2)(3), up until the heap, leaving only one element.
Heap sort algorithm performance analysis:
Space complexity: o (1);
Time Complexity: built heap: o (n), each adjustment o (log n), it is the best, the worst, the average case: o (n * logn);
Stability: Unstable
Establish large root heap method:
// Build large root heap: the array as a complete binary tree structure stored in the order
private int [] buildMaxHeap (int [] array) {
// Start from the last node of the parent node array.length1 (array.length11) / 2, until the root 0, repeatedly adjust the heap
for (int i = (array.length2) / 2; i> = 0; i ) {
adjustDownToUp (array, i, array.length);
}
return array;
}
// The element array [k] from the bottom up gradually adjust the tree structure
private void adjustDownToUp (int [] array, int k, int length) {
int temp = array [k];
for (int i = 2 * k + 1; i < length1; i = 2 * i + 1) {// i is initialized to the left child node k, node along the larger child node downward adjustment
if (i < length && array [i] < array [i + 1]) {// get the larger node child node subscript
i ++; // if the right child node> left child, then take the right child node subscript
}
if (temp> = array [i]) {// root node> = about children keyword is greater, the adjustment is completed
break;
} Else {// the root < children around the greater keyword
array [k] = array [i]; // left and right child nodes is greater array [] adjusted to the parent node
k = i; // [key] to modify the value of k, to continue to adjust downward
}
}
array [k] = temp; // value to be adjusted node release the final position
}
HEAPSORT:
// Heap sort
public int [] heapSort (int [] array) {
array = buildMaxHeap (array); // initial construction heap, array [0] for the first trip to the value of the largest element
for (int i = array.length1; i> 1; i ) {
int temp = array [0]; // the top of the heap and stack elements low exchange element, to obtain the correct current ranking position of the largest element
array [0] = array [i];
array [i] = temp;
adjustDownToUp (array, 0, i); // sort the remaining elements of finishing piles
}
return array;
}
Remove top of the heap element (ie, the maximum value of the sequence): The last element of the first stack element exchange with the top of the heap, because this time the nature of the heap is destroyed, the need for this time of the root node downward adjustment operation.
// Delete the top of the heap element operation
public int [] deleteMax (int [] array) {
// The last element of the heap and stack top element of the exchange, the end of the heap element value is set to 99999
array [0] = array [array.length1];
array [array.length1] = 99999;
// At this time of the root node downward adjustment
adjustDownToUp (array, 0, array.length);
return array;
}
Insertion operation of the heap: first new node on the end of the stack, and then adjust the operation of the new node performs upward.
The last element of the array is assumed that array [array.length1] is empty, the new node is inserted initially placed here.
// Insert: To a large root heap array insert data data
public int [] insertData (int [] array, int data) {
// The new node on the end of the heap; array [array.length1] = data
int k = array.length1; // nodes need to be adjusted
int parent = (k1) / 2; // parent node
while (parent> = 0 && data> array [parent]) {
array [k] = array [parent]; // parent node down
k = parent;
if (parent! = 0) {
parent = (parent1) / 2; // continue upward comparison
} Else {// root node has been adjusted, out of the loop
break;
}
}
array [k] = data; // The node is inserted into the correct position
return array;
}
test:
public void toString (int [] array) {
for (int i: array) {
System.out.print (+ "");
}
}
public static void main (String args []) {
HeapSort hs = new HeapSort ();
int [] array = {87,45,78,32,17,65,53,9,122};
System.out.print ( "build large root heap:");
hs.toString (hs.buildMaxHeap (array));
System.out.print ( "\ n" + "delete the top of the stack elements:");
hs.toString (hs.deleteMax (array));
System.out.print ( "\ n" + "insert element 63:");
hs.toString (hs.insertData (array, 63));
System.out.print ( "\ n" + "large root heap sort:");
hs.toString (hs.heapSort (array));
}
Construction of large root heap 1: 122 877,845,176,553,932
2 Remove the top of the heap element: 874,578,321,765,539 99999
3 Insert Element 63:87 637,845,176,553,932
4 large root heap sort: 9 1,732,455,363,657,887 


