Heap sort summary

The content of this paper comes from 《 Comics algorithm 》 And data structure textbook
The heap mentioned here is a binary heap , It is essentially a complete binary tree . Heap sorting only requires an auxiliary space of record size .
1.java Realization

	/** *  Sinking adjustment  * @param arr  The heap to be adjusted  * @param parentIndex  Subscript of parent node to sink  * @param length  The effective size of the heap ( Generally refers to the array length of the storage heap ) */
	void downAdjust(int[] arr, int parentIndex, int length) {
    
		// temp Save the value of the parent node , For the final assignment 
		int temp = arr[parentIndex];
		int childIndex = 2 * parentIndex + 1;
		while (childIndex < length) {
    
			//  If there is rightChild, also rightChild Greater than leftChild value , be childIndex Point to rightChild
			if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
    
				childIndex++;
			}

			//  If the parent node is larger than the largest element in the child node , And then jump out of the loop , Because there is no need to sink 
			if (temp >= arr[childIndex])
				break;

			//
			arr[parentIndex] = arr[childIndex];
			parentIndex = childIndex;
			childIndex = 2 * childIndex + 1;
		}
		arr[parentIndex] = temp;
	}
	
	/** *  Heap sort ( Ascending ) * @param arr  The heap to be adjusted  */
	void heapSort(int[] arr) {
    
		// 1. Build an unordered array into a maximum heap [ From the last non-leaf node , Carry out sinking adjustment one by one ]
		for (int i = (arr.length - 2) / 2; i >= 0; i--) {
    
			downAdjust(arr, i, arr.length);
		}
		System.out.println(Arrays.toString(arr));
		// 2. Loop delete ( Not really delete , Just move to the end ) Heap top element , Move to the end of the assembly , Adjust the heap to produce a new top 
		for (int i = arr.length - 1; i > 0; i--) {
    
			//  The last element is swapped with the first 
			int temp = arr[i];
			arr[i] = arr[0];
			arr[0] = temp;
			//  Sinking adjustment 
			downAdjust(arr, 0, i);
		}
	}
	
	@Test
	public void fun1() {
    
		int[] arr = new int[] {
     1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

2.C Language implementation

/* *  The implementation of heap sorting  *  data structure (C Language version )  YanWeiMin   Wei-min wu  *  Realizing heap sorting needs to be solved 2 A question ： (1) How to build a heap from an unordered sequence ？ (2) How do I do this after the output heap top element , Adjust the remaining elements into a new heap ？ */
#include<iostream>
using namespace std;

/*  Adjustment of pile  s  Root node index  m  The effective length of the array   Adjust to large top reactor  */
void HeapAdjust(int arr[], int s, int m) {
    
	//cout<<"m"<<m<<endl;
	//  Save the nodes that need to be adjusted 
	int temp = arr[s];

	for (int j = 2 * s + 1; j <= m; j = 2 * j + 1) {
     //  Along the key Older child nodes are filtered down 
		/* cout<<"parent "<<arr[s]<<endl; cout<<"left "<<arr[j]<<endl; if(j+1<=m) cout<<"right "<<arr[j+1]<<endl; else cout<<"right"<<" is empty"<<endl; cout<<"+"<<j<<endl; */
		if (j < m && arr[j] < arr[j + 1]) // j by key Subscripts of larger records 
			++j;
		//cout<<"="<<j<<endl;
		if (temp > arr[j]) {
    
			//cout<<temp<<"gt"<<arr[j]<<" end for loop"<<endl;
			break;
		}
		arr[s] = arr[j]; //  Larger nodes " Go up "
		/*  Omit here arr[j]=temp; This step is redundant ,  Just perform this step at the end , Will the original s Put the element pointed to in the final position  */
		arr[j] = temp; //(1) You can add this sentence when debugging , It is convenient to view the final result 
		s = j; //  The parent node index points to the newly adjusted j Location 
	}
	arr[s] = temp; // If there is no data exchange in the loop , This step is unnecessary , There's nothing wrong with it .
	//cout<<"**********************"<<endl;
}

void HeapSort(int arr[]) {
    
	// 1. Build heap ( This pile is a binary pile , The essence is a complete binary tree )
	int len = 8;
	for (int i = len / 2 - 1; i >= 0; --i) {
    
		HeapAdjust(arr, i, len - 1);
	}
	cout << "-------------------------" << endl;
	// 2. Adjust the remaining elements into a new heap 
	for (int i = len - 1; i > 0; --i) {
    
		//  Heap top elements and currently unordered subsequences arr[0..i] The last record in is exchanged with each other 
		int temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;

		HeapAdjust(arr, 0, i - 1); //  take arr[0..i-1] Readjustment to the big top 
	}

}

int main(int argc, char* argv[]) {
    
	int arr[] = {
     49, 38, 65, 97, 76, 13, 27, 49 };
	HeapSort(arr);

	int len = 8;
	for (int i = 0; i < len; i++) {
    
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

Practice of heap sorting java edition [ Comics algorithm ]
Heap is essentially a complete binary tree , Store... In an array ,
parent,leftChild,rightChild
The relationship of array subscripts between them is as follows ：
$\{\begin{array}{l}leftChild=2\ast parent+1;\\ rightChild=2\ast parent+2;\end{array}$

---

Heap sort algorithm steps
1. Building an unordered array into a binary heap .
2. Loop to delete the top element , And move the element to the end of the collection , Adjust the heap to produce a new top .
( The deletion here is not true, it just moves to the corresponding position behind the array )

Time complexity O(nlogn)
Spatial complexity O(1)

---

Macroscopically, the similarities and differences between heap sort and quick sort
The same thing ,1. The average time complexity of heap sort and quick sort is O(nlogn), And they are all unstable sorting .
Difference ,1. The worst time complexity of quicksort is O(n^2); The worst-case time complexity of heap sorting is stable O(nlogn)
2. In addition, the space complexity of recursive and non recursive methods of fast sorting is O(logn),
And the spatial complexity of heap sorting is O(1)

In comic Algorithm , There are many schematic diagrams of heap adjustment , It's very helpful to understand .

---

The heap is defined as follows ：n A sequence of elements $\{k_1,k_2,...,k_n,\}$ If and only if the following relationship is satisfied , Called the heap . The subscript of the textbook definition here is from 1 At the beginning , The subscript of the actual program is from 0 At the beginning , Attention switching
$\{\begin{array}{l}{k}_i⩽k_{2i}\\ k_i⩽k_{2i+1}\end{array}$ or $\{\begin{array}{l}{k}_i⩾k_{2i}\\ k_i⩾k_{2i+1}\end{array}$
$(i=1,2,...,\lfloor \frac{n}{2}\rfloor )$
If a one-dimensional array corresponding to this sequence （ That is, a one-dimensional array is used as the storage structure of this sequence ） Think of it as a complete binary tree , Then the meaning of the heap table name , All in a complete binary tree Non terminal nodes The values of are not greater than （ Or not less than ） The value of the left and right child nodes . thus , If sequence $\{k_1,k_2,...,k_n,\}$ Is a pile of , Then the top element （ Or the root of a completely binary tree ） Must be in sequence n The minimum number of elements （ Or maximum ）.
The definition of comic algorithm is relatively simple and easy to understand . The textbook definition is too complex and frightening .