Java Implement heap sort （ Big root pile ）

Heap sort is a tree selection sort method , It is characterized by ： In the sort process , take array[0,…,n-1] See it as a The sequential storage structure of a complete binary tree , The intrinsic relation between parent node and child node in a complete binary tree is used , Select the keyword maximum in the current unordered area （ Minimum ） The elements of .

1. if array[0,…,n-1] Represents the sequential storage pattern for a complete binary tree , Then the internal relationship between parent node pointer and child node pointer is as follows ：

Any node pointer i： Parent node ：i==0 ? null : (i-1)/2

  Left the child ：2*i + 1

  The right child ：2*i + 2

2. The definition of the heap ：n A sequence of keywords array[0,…,n-1], If and only if the following requirements are met ：(0 <= i <= (n-1)/2)

① array[i] <= array[2*i + 1] And  array[i] <= array[2*i + 2]; It’s called a root heap ;

② array[i] >= array[2*i + 1] And  array[i] >= array[2*i + 2]; It’s called the big root heap ;

3. Create a large root heap ：

n A complete binary tree of nodes array[0,…,n-1], The last node n-1 It’s No (n-1-1)/2 Children of nodes . Right. (n-1-1)/2 Subtree adjustment with nodes of root , Make the subtree called a heap .

For the big root heap , Adjustment method by ： if 【 The keyword of the root node 】 Less than 【 About the children of the larger keyword 】, The exchange .

And then you go forward to each node （(n-2)/2 – 1）~ 0 Make adjustments for the root’s subtree , See if the value of the node is greater than the value of its left and right child nodes , If it is not , The larger values in the left and right child nodes are swapped with it , The next level of the heap may be destroyed after the swap , We continue to build the next level of the heap in the same way , Until the subtree with the node as root constitutes the heap .

The above method of adjusting the heap is used repeatedly to build the heap , All the way to the root .

4. Heap sort ：（ Big root pile ）

① Will be stored in array[0,…,n-1] Medium n The elements are built into the initial heap ;

② Swap the top and bottom elements of the heap , Then the maximum value of the sequence is in the correct position ;

③ But now the heap is broken , Adjust the top of the heap element downward so that it continues to be a large root heap , Repeat the first ②③ Step , Until there is only one element left in the heap .

Performance analysis of heap sort algorithm ：

Spatial complexity :o(1);

Time complexity : Building the heap ：o(n), Every time to adjust o(log n), So the best 、 The worst 、 On average ：o(n*logn);

stability ： unstable

The way to build a big pile ：

// Build a large root heap ： take array Think of it as a sequential storage structure for a complete binary tree
private int[] buildMaxHeap(int[] array){
// From the last node array.length-1 Parent node （array.length-1-1）/2 Start , All the way to the root 0, Repeatedly tuned reactor
for(int i=(array.length-2)/2;i>=0;i--){
adjustDownToUp(array, i,array.length);
}
return array;
}
// Put the element array[k] Adjust the tree gradually from the bottom up
private void adjustDownToUp(int[] array,int k,int length){
int temp = array[k];
for(int i=2*k+1; i<length-1; i=2*i+1){ //i Is initialized as a node k The left child , Adjust downward along the larger children of the node
if(i<length && array[i]<array[i+1]){ // Takes the subscript of the larger child of the node
i++; // If the node's right child > Left the child , Then take the subscript of the right child node
}
if(temp>=array[i]){ // The root node >= About the children of the larger keyword , Adjust the end
break;
}else{ // The root node < About the children of the larger keyword
array[k] = array[i]; // Make the left and right children larger array[i] Adjust to the parent node
k = i; //【 The key 】 modify k value , In order to continue to adjust down
}
}
array[k] = temp; // The value of the node being adjusted is placed at its final position
}

  Heap sort ：

// Heap sort
public int[] heapSort(int[] array){
array = buildMaxHeap(array); // Established at the beginning of the heap ,array[0] Is the element with the largest value in the first pass
for(int i=array.length-1;i>1;i--){
int temp = array[0]; // Swap the top and bottom elements of the heap , That is, the correct sorting position of the current largest element
array[0] = array[i];
array[i] = temp;
adjustDownToUp(array, 0,i); // Arrangement , Pile up the remaining elements
}
return array;
}

  Remove the heap top element （ The maximum value in the sequence ）： First, exchange the last element of the heap with the top element , Because the nature of the heap is destroyed , You need to adjust the root node downward at this time .

// Remove the heap top element operation
public int[] deleteMax(int[] array){
// Swaps the last element of the heap with the top element of the heap , The heap base element value is set to -99999
array[0] = array[array.length-1];
array[array.length-1] = -99999;
// Adjust the root node downward at this point
adjustDownToUp(array, 0, array.length);
return array;
}

Insert operation on the heap ： First put the new node at the end of the heap , Then perform the up adjustment operation on this new node .

Suppose the last element of the array array[array.length-1] It’s empty , The newly inserted node is initially placed here .

// The insert : To the big root pile array Insert data data
public int[] insertData(int[] array, int data){
array[array.length-1] = data; // Place the new node at the end of the heap
int k = array.length-1; // Nodes that need to be adjusted
int parent = (k-1)/2; // parent node
while(parent >=0 && data>array[parent]){
array[k] = array[parent]; // Parent node down-regulation
k = parent;
if(parent != 0){
parent = (parent-1)/2; // Keep going up
}else{ // The root node has been adjusted , Out of the loop
break;
}
}
array[k] = data; // Put the inserted node in the correct position
return array;
}

  test ：

public void toString(int[] array){
for(int i:array){
System.out.print(i+" ");
}
}
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 a large root heap ：");
hs.toString(hs.buildMaxHeap(array));
System.out.print("\n"+" Remove the heap top element ：");
hs.toString(hs.deleteMax(array));
System.out.print("\n"+" Insert elements 63:");
hs.toString(hs.insertData(array, 63));
System.out.print("\n"+" Big root heap sort ：");
hs.toString(hs.heapSort(array));
}

1 Build a large root heap ：122 87 78 45 17 65 53 9 32
2 Remove the heap top element ：87 45 78 32 17 65 53 9 -99999
3 Insert elements 63:87 63 78 45 17 65 53 9 32
4 Big root heap sort ：9 17 32 45 53 63 65 78 87