1. Basic introduction to heap sorting

  1. Heap sort is the use of heap data structure and design of a sort algorithm, heap sort is a choice sort, its worst, best, average time complexity is O(nlogn), it is also unstable sort.

  2. A heap is a complete binary tree with the property that the value of each node is greater than or equal to the value of its left and right children, called the big top heap. Note: there is no requirement for the relationship between the value of the left child and the value of the right child.

  3. The value of each node is less than or equal to the value of its left and right children, called the small top heap

  4. The big top heap is an example

  1. Small top heap as an example

  1. In general, large top heap is used for ascending and small top heap is used for descending

2. Basic idea of heap sort

  1. The sequence to be sorted is constructed as a large top heap

  2. At this point, the maximum value of the entire sequence is the root node at the top of the heap.

  3. Swap it with the trailing element, where the trailing element is the maximum.

  4. The remaining n-1 elements are then reconstructed into a heap, which yields the subsmallest values of n elements. Do this repeatedly, and you get an ordered sequence.

You can see that as you build the big top heap, the number of elements gets smaller and smaller, and you end up with an ordered sequence.

3. Diagram of heap sorting steps

Request: give you an array {4,6,8,5,9}, ask to use heap sort, the array ascending sort.

Step 1: Construct the initial heap. The given unordered sequence is constructed into a big top heap (generally the big top heap is used for ascending order and the small top heap is used for descending order).

  1. At this point we start from the last non-leaf node (leaf node naturally need not adjust, the first non-leaf node arr. Length /2-1=5/2-1=1, namely the following 6 nodes), from left to right, from bottom to top to adjust.

  1. Find the second non-leaf node 4, since the element 9 in [4,9,8] is the largest, 4 and 9 are swapped.

  1. At this time, swapping leads to structural disorder of the child roots [4,5,6], further adjustment,6 is the largest in [4,5,6], and swapping 4 and 6.

At this point, we construct a large top heap from an unordered sequence.

Step two swaps the top element with the end element to maximize the end element. We then continue to adjust the heap, swapping the top element with the bottom element to get the second largest element. And so on and so forth.

  1. .swap the top element 9 with the bottom element 4

  1. . Readjust the structure so that it continues to meet the heap definition

  1. . Then swap the top element 8 with the bottom element 5 to get the second largest element 8.

  1. The follow-up process, continue to adjust, exchange, so repeated, eventually making the sequence order

The basic idea of heap sorting is summarized briefly:

1). Build a heap of unordered sequences, and select a big top heap or a small top heap according to ascending and descending requirements;

2). Swap the top element with the end element, and “sink” the largest element to the end of the array;

3). Rearrange the structure so that it meets the heap definition, and then continue to swap the top element with the current end element, repeating the adjust + swap step,

Until the whole sequence is ordered.

Code 4.

1. Adjust an array (binary tree) to a large top heap

	Int arr[] = {4, 6, 8, 5, 9}; int arr[] = {4, 6, 8, 9}; => I = 1 => adjustHeap => get {4, 9, 8,5, 6} * If we call adjustHeap again with I => get {4, 9, 8,5, 6} => {9,6,8,5, 4} *@paramArr Array to be adjusted *@paramI indicates that the non-leaf node is indexed * in the array@paramLenght indicates how many elements continue to be adjusted, and the length is gradually reduced */
	public  static void adjustHeap(int arr[], int i, int lenght) {
		
		int temp = arr[i];// First fetch the value of the current element, save in a temporary variable
		// Start adjusting
		/ / that
		//1. K = I * 2 + 1
		for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
			if(k+1 < lenght && arr[k] < arr[k+1]) { // Indicates that the value of the left child is smaller than that of the right child
				k++; // k points to the right child
			}
			if(arr[k] > temp) { // If the child is larger than the parent
				arr[i] = arr[k]; // Assign the larger value to the current node
				i = k; / /!!!!!! I points to k, and we keep going
			} else {
				break;/ /!}}// When the for loop ends, we have placed the maximum value of the tree with parent I at the top (local).
		arr[i] = temp;// Put the temp value in the adjusted position
	}
	
Copy the code

2. Write a heap sort method

public static void heapSort(int arr[]) {
		int temp = 0;
		System.out.println("Heap sort!!");
		
// // step by step
// adjustHeap(arr, 1, arr.length);
// system.out.println (" first "+ array.toString (arr)); // 4, 9, 8, 5, 6
//		
// adjustHeap(arr, 0, arr.length);
// system.out.println (" 通 行 "+ array.toString (arr)); / / 9,6,8,5,4
		
		// Finish our final code
		// Build the unordered sequence into a heap, and select a large or small top heap according to ascending or descending requirements
		for(int i = arr.length / 2 -1; i >=0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		
		/* * 2). Swap the top element with the end element, and "sink" the largest element to the end of the array; 3). Rearrange the structure so that it meets the heap definition, and then continue swapping the top element with the current end element, repeating the adjust + swap step until the whole sequence is in order. * /
		for(int j = arr.length-1; j >0; j--) {
			/ / exchange
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j); 
		}
		
		Println (" Array =" + Arrays. ToString (arr)); //System.out.println(" array =" + Arrays.
		
	}
Copy the code

3. The test

int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // Generate a [0, 8000000) number
		}

		System.out.println("Pre-sort");
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("The time before sorting is equal to" + date1Str);
		
		heapSort(arr);
		
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("The time before sorting is equal to" + date2Str);
Copy the code