Heap sort is a kind of selective sort which takes advantage of the properties of heap.

Time complexity:

  • Time complexity: O(nlogn)
  • Space complexity: O (1) (Sort in place, auxiliary space for heapification (also known as filtering))

Performance:

  1. Heap sort is not suitable for those with fewer records because of the number of comparisons required to build the initial heap.

  2. The time of heap sort is mainly composed of the time cost of building the initial heap and rebuilding the heap repeatedly.

  3. Heap sort is an unstable sort. The stability of sorting means that if there are two elements in the same sequence, their relative positions do not change before and after sorting.

  4. Even in the worst case the heapsort time complexity is O(nlogn). Quicksort is O(N^2) in the worst case, so quicksort is faster in the best and average case than heap, and heap is faster in the worst case than quicksort.

Basic idea:

Taking advantage of the fact that the top of the heap records the largest (small) keyword makes it easy to select the largest (small) record from the disorder each time.

The following discussion is entirely based on the big top heap (the same goes for the small top heap).

  1. Initialize the keyword sequence to be sorted (R1,R2…. Rn) is constructed into the big top heap, which is the initial unordered region;

  2. The top element R[1] is swapped with the last element R[n], and a new unordered region (R1,R2,……) is obtained Rn-1) and a new ordered region (Rn), and R[1,2…n-1]<=R[n];

  3. Since the new heap top R[1] after the swap may violate the heap properties, the current unordered region (R1,R2,……) is required Rn-1) adjusts to the new heap (heapized, filtered), and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2…. Rn-2) and the new ordered region (Rn-1,Rn). This process is repeated until the number of ordered elements is n-1 (the last element left in the heap), and the sorting process is complete.

The operation process is as follows:

  1. Initialize heap: construct R[1..n] as heap;

  2. Swap the heap top element R[1] of the current unordered region with the last record between the regions, and then adjust the new unordered region to the new heap (continuously heaped).

Therefore, for heap sorting, the two most important operations are constructing the initial heap and adjusting the heap. In fact, constructing the initial heap is actually the process of adjusting the heap, but constructing the initial heap is adjusting all the non-leaf nodes.

Given an integer array a[]={16,7,3,20,17,8}, heap sort it.

Firstly, a complete binary tree is constructed according to the array element, and then:

Then the initial heap needs to be constructed, and the adjustment starts from the last non-leaf node. The adjustment process is as follows:

#### The following is to construct the initial heap:

  1. 8 and 3 swap, satisfy;

  2. 20 and 7 are swapped so that 20 and 16 are not satisfied;

  1. 20 and 16 are swapped so that 17 and 16 are not satisfied;
  2. 17 and 16 swap;

  1. Complete the build (big top heap).

That is, each adjustment is from the parent node, left child node, right child node three choose the largest with the parent node for exchange (exchange may cause the child node to be exchanged does not meet the nature of the heap, so after each exchange to be re-adjusted to the child node to be exchanged). Once you have your initial heap, you can sort.

The following elements are exchanged and heaped at each step:

  1. Swap 3 and 20; The diagram below:

At this time, the position of 3 at the top of the heap is not enough for the nature of the large top heap, so it needs to continue to adjust. Exchange 3 and 17, resulting in 3 and 16 are not satisfied; Swap 3 and 16; Meet;

  1. Swap 17 and 3; The diagram below:

At this time, the position of 3 at the top of the heap is not enough for the nature of the large top heap, so it needs to continue to adjust. Exchange 3 and 16, resulting in 3 and 7 are not satisfied; Swap 3 and 7; Meet;

3. Swap 16 and 3. As shown in the figure below: at this time, the position of 3 on the top of the heap is not enough for the nature of the large top heap, so it needs to continue to adjust. Swap 3 and 8; Meet;

4. Swap 3 and 8; As shown in the figure below: at this time, the position of 3 on the top of the heap is not enough for the nature of the large top heap, so it needs to continue to adjust. Swap 3 and 7; Meet;5. Swap 3 and 7; As shown below: If yes, the sorting is complete.

So the whole interval is already in order.

As can be seen from the above process, heap sort is actually a selection sort, which is a tree selection sort. However, in direct selection sort, n-1 times is required to select the maximum record from R[1…n], and n-2 times is required to select the maximum record from R[1…n-2]. In fact, many of the n-2 comparisons have been done in the previous N-1 comparison, and the tree selection sort just takes advantage of the characteristics of trees to save part of the previous comparison results, so the number of comparisons can be reduced. For n keyword sequences, each node needs to be compared logn times in the worst case, so its time complexity is nlogn in the worst case.

Algorithm implementation (Java) :

/** define Heap */ static class Heap{int count; public int[] Array; public Heap(int count){ this.count=count; this.Array=new int[count]; } public int getLeft(int I){int left=2* I +1; if(this.Array==null || left>=this.count){return -1; } return left; } public int getRight(int I){int right=2* I +2; if(this.Array==null || right>=this.count){return -1; } return right; } public void PercolateDown(int I){int left,right, Max = 0,temp; left=this.getLeft(i); right=this.getRight(i); if(left! =-1 && this.Array[i]>=this.Array[left]){ max=i; }else{ max=left; } if(right! =-1 && this.Array[right]>this.Array[max]){ max=right; } // exchange, end the method after exchange, external call if(Max! =-1 && max! =i){ temp=Array[max]; Array[max]=Array[i]; Array[i]=temp; PercolateDown(max); } } } public static Heap Heapsort(int[] A,int n){ Heap heap=new Heap(n); int temp; for(int i=0; i<n; i++){ heap.Array[i]=A[i]; } for(int I =(n-1)/2; i>=0; i--){ heap.PercolateDown(i); } for(int I =n-1; i>=0; I --){// heap.array [0] Stores the largest element temp= heap.array [0]; heap.Array[0]=heap.Array[i]; heap.Array[i]=temp; Heap. count--; heap.count--; heap.count--; // Heap heap.PercolateDown(0); } return heap; }Copy the code

Test procedure:

Public static void main(String[] arg){int[] A=new int[]{5,14,78,2,14,53,45,1}; long time1=System.nanoTime(); Heap heap=Heapsort(A, A.length); System.out.println(System.nanoTime()-time1); for (int j : heap.Array) { System.out.println(j); }}Copy the code

Print the following:

70936
1
2
5
14
14
45
53
78
Copy the code

QQ(skirt) : 985600592