To learn heap sorting, you must first understand the concept of heap. Heap is an array. It can be approximate as an array storage method as a completely binary tree. But there are other properties with him, which are similar to binary sorting trees. There are differences between the largest heap and the smallest heap. The largest heap means that the value of the root node is greater than the value of the child node, while the smallest heap means that the value of the root node is less than the value of its child node. Heap sorting generally uses the largest heap, while the smallest heap can construct a priority queue. There is a method in the heap that is used to maintain the properties of the heap, which is the maxheap method in our code below. This is the method to maintain the maximum heap properties. The first parameter is the heap, that is, the array, and the second parameter is to adjust the heap. For specific node location, the value of this node may not conform to the nature of the maximum heap, so this value position is used as a parameter, and size is actually the number of valid elements actually stored in the heap. Maybe the length of the array is the number of elements actually stored in the heap, but not necessarily all data we need to build the maximum heap. The introduction to the algorithm says that the left sub-node is 2xi, but our array counts from 0, so the left sub-node becomes 2xi+1. Buildheap is to build a maximum heap. The reason why we go to the length of 2 is ,The child nodes of these points are all leaf nodes, so we build a maximum heap by sorting it from bottom to top. Ensure that all nodes in our heap meet the maximum heap properties. Finally, heap sorting is to take out the first node, sort the remaining nodes again, and then take out the root node. This ensures that every time we take it out, it is the maximum value.
The code copy is as follows:
public class HeapSort {
private int getLeft(int i){
return 2*i+1;
}
private int getRight(int i){
return 2*i+2;
}
public void maxheap(int[] heap,int loc,int size){
int l=getLeft(loc);
int r=getRight(loc);
int largest=loc;
if(l<size&&heap[l]>heap[loc]){
Largest=l;
}
if (r<size&&heap[r]>heap[largest]) {
Largest=r;
}
if(largest!=loc){
int cache=heap[loc];
heap[loc]=heap[largest];
heap[largest]=cache;
maxheap(heap, large, size);
}
}
public void buildheap(int[] heap){
for(int i=heap.length/2;i>=0;i--){
maxheap(heap, i, heap.length);
}
}
public void sort(int[] heap){
buildheap(heap);
for(int i=heap.length-1;i>1;i--){
int cache=heap[0];
heap[0]=heap[i];
heap[i]=cache;
maxheap(heap, 0,i);
}
int cache=heap[0];
heap[0]=heap[1];
heap[1]=cache;
}
public static void main(String[] args) {
int[] heap=new int[]{4,1,5,3,7,12,65,7};
HeapSort hs=new HeapSort();
hs.sort(heap);
for (int i = 0; i < heap.length; i++) {
System.out.println(heap[i]);
}
}
}