Reference blog: www.cnblogs.com/lyw-hunnu/p…

The above blog has introduced a very detailed, write about the implementation process encountered problems.

heapInsert

HeapInsert: Appends an element to the end of an existing large root heap, then restructures it to remain the large root heap. The code is as follows:

    public static void heapInsert(int[] array,int index){   
    // The appended number has already been appended to the end of the array. You need to adjust the position of the number
        while (array[index] > array[(index - 1) /2]) {
            // Stop condition 1: The new node is no longer larger than the parent node
            // Stop condition 2: the root of the entire tree has been reached
            swap(array, index, (index - 1) /2);
            index = (index - 1) /2; }}Copy the code

Note that there are two termination conditions for the while loop.

1. The new node is no longer larger than the parent node.

2. The root node 0 of the entire tree has been reached.

But when index=0, (0-1)/2=0, so arr[index] arr[(index-1)/2] is equal. In other words, the quotient of a over b will round up to 0, so negative numbers round up, positive numbers round down, kind of like rounding.

heapify

Heapify: After popping out the maximum size of the large root heap, adjust the heap structure to remain the large root heap. In this case, the root node of the large root heap is obviously not the maximum and the element needs to be sunk. Heapify is an element sinking operation. The code is as follows:

public static void heapify(int[] array, int index, int heapSize){ int left = index * 2 + 1; While (left < heapSize){// Compare values between left and right children: Largest = left int largest= left + 1 < heapSize && array[left + 1] > array[left]? left + 1 : left; Largest = array[largest] > array[index]? largest : index; if (largest == index) { break; } swap(array, largest, index); index = largest; left = index * 2 + 1; }}Copy the code

Write your own feeling than the above code ideas a lot of chaos, or use the above method, get used to it.

Heap sort

With heapInsert and Heapify above, you can do heap sort. Heap sort is as follows:

1. Given an array array, first go through the array, perform heapInsert on each element of the array, generate a large root heap, and get size.

2. Swap the root element of the generated large root heap with the last element (because the root element must be the maximum). At the same time –size moves the maximum value already determined out of the heap structure. Heapify the elements swapped to the root node location.

2. Repeat step 2 until the heap structure is empty. The code is as follows:

	public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			heapInsert(arr, i);
		}
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
	
Copy the code