ACM tutorial - heap sorting

Definition

Heap is a data structure called complete binary tree . Here we use two types of piles , In fact, it's a kind of .

• Big pile top ： The value of each node is greater than or equal to the value of its left and right child nodes .
• Small cap pile ： The value of each node is less than or equal to the value of its left and right child nodes .

​

Ps： Small top stack error , node 3 and node 2 Change position ！

As shown above , There are two kinds of piles . If we map this logical structure to Array in , It's just like this below

9

5

8

2

3

4

7

1

1

2

5

4

3

8

9

7

This array arr Logically, it's a heap . From here we can draw the following properties （ a key ）

1. For the big top heap ：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
2. For a small top pile ：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

• stability ： according to   Equivalent element   In the array   Relative order   Is it changed , Sorting algorithms can be divided into 「 Stable sequencing 」 and 「 Unstable ordering 」 Two types of .
• Locality ： According to the sorting process   Whether to use additional memory （ Auxiliary array ）, Sorting algorithms can be divided into 「 In situ sorting 」 and 「 Offsite sorting 」 Two types of . In a general way , Since no external memory is used , Sorting in place is more efficient than sorting not in place .
• Self adaptability ： According to the algorithm   Time complexity   whether   Affected by the element distribution of the array to be sorted  , Sorting algorithms can be divided into 「 Adaptive sorting 」 and 「 Non adaptive sorting 」 Two types of .「 Adaptive sorting 」 The time complexity of is affected by the element distribution , On the contrary, it will not be affected .
• Comparative ： The sort of comparison classes is based on   Comparison operator （ Less than 、 equal 、 Greater than ） To determine the relative order of elements ; Relative , Non comparison sorting is not based on comparison operator .

The illustration

4

5

8

2

3

9

7

1

Take this array as an example , Build the largest heap to sort from small to large , The main points are as follows

1. Build the maximum heap at the beginning , From the last non leaf node to the root node （ From bottom to top , From right to left ）
2. When it's your turn （ Currently viewed as a parent node ）, Compare your left child node with your right child node , Finally, the largest node is determined , If the largest node is itself , Don't swap ; Otherwise, you can exchange your own node with the largest node
3. If the first 2 There is no exchange at the point （ Skip the first 3 spot ）, Otherwise, continue to replace the child nodes （ It was originally the parent node , That's right. ）, Continue to maintain the same comparison operation , Until there are no nodes

• The above maximum heap construction is completed , Next, start the real heap sort , First build complete , The root node must be the maximum , Change to the last 1 A leaf node , At the end of the day 1 Nodes to the root node , Then maintain the heap , Then the second 2 A maximum of , Then switch the root node to the penultimate node again 2 A leaf node , And so on . complete （ Because the space is limited , Only the key intermediate process legends in the explanation are listed ）

  

nature

• Time complexity
  • The best O(nlogn)
  • Average O(nlogn)
  • The worst O(​​​​​​​nlogn)
• Spatial complexity
  • The worst O(1)
• stability ： unstable
• Locality ： In situ
• Self adaptability ： The adaptive
• Comparative ： Compare  

Java

public class HeapSort {
 
    //  The entrance is here 
	public static void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		//  Build the big top heap , This is actually the sequence to be sorted , Into an array of large top heap structures 
		buildMaxHeap(arr, len);
 
		//  Swap nodes at the top of the heap and at the current end , Reset the big top stack 
		for (int i = len - 1; i > 0; i--) {
			swap(arr, 0, i);
			len--;
			heapify(arr, 0, len);
		}
	}
 
	private static void buildMaxHeap(int[] arr, int len) {
		//  Traverse forward from the last non leaf node , Adjust node properties , Make it a big top pile 
		for (int i = (len - 1) / 2; i >= 0; i--) {
			heapify(arr, i, len);
		}
	}
 
	private static void heapify(int[] arr, int i, int len) {
		//  First, according to the nature of the heap , Find the index of its left and right nodes 
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		//  The default is the current node （ Parent node ） Is the maximum value. .
		int largestIndex = i;
		if (left < len && arr[left] > arr[largestIndex]) {
			//  If there is a left node , And the value of the left node is larger , Update the index of the maximum value 
			largestIndex = left;
		}
		if (right < len && arr[right] > arr[largestIndex]) {
			//  If there is a right node , And the value of the right node is greater , Update the index of the maximum value 
			largestIndex = right;
		}
 
		if (largestIndex != i) {
			//  If the maximum value is not the value of the current non leaf node , Then swap the values of the current node and the child node of the maximum value 
			swap(arr, i, largestIndex);
			//  Because after the exchange , The value of the child node changes , If the child node also has its own child node , It still needs to be adjusted again .
			heapify(arr, largestIndex, len);
		}
	}
 
	private static void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}