Heap sorting learning

Heapsort

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. Heap sort can be said to be a selection sort that uses the concept of heap to sort. There are two methods:

1. Large top heap: Each node has a value greater than or equal to the value of its children, used in ascending heap sorting;

2. Small top heap: The value of each node is less than or equal to the value of its children, used in descending order in the heap sort algorithm;

Algorithm description

1. Create a heap H[0…… n-1];
2. Swap the heap head (maximum) with the heap tail;
3. Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.
4. Repeat step 2 until the heap size is 1.

example

Array:4 6 8 5 9For the first time:4 6 8 5 9= = = > > >4 9 8 5 6The second:4 9 8 5 6= = = > > >9 4 8 5 6The third time:9 4 8 5 6= = = > > >9 6 8 5 4For the fourth time:9 6 8 5 4= = = > > >4 6 8 5 9Fifth:4 6 8 5 9= = = > > >8 6 4 5 9Sixth:8 6 4 5 9= = = > > >5 6 4 8 9Seventh:5 6 4 8 9= = = > > >6 5 4 8 9Eighth:6 5 4 8 9= = = > > >4 5 6 8 9In the end4 5 6 8 9The end of theCopy the code

Algorithm complexity

Space complexity: O(1)

Time complexity:

Sorting is unstable, and the first two arguments that were equal may be next.

Code implementation

public static void sort(int[] sourceArray) throws Exception {
  // Copy the arR without changing the parameters
  int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  int len = arr.length;
  buildMaxHeap(arr, len);
  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) {
  for (int i = (int) Math.floor(len / 2); i >= 0; i--) { heapify(arr, i, len); }}private static void heapify(int[] arr, int i, int len) {
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  int largest = i;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest != i) {
    swap(arr, i, largest);
    heapify(arr, largest, len);
  }
}

private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
  System.out.println(Arrays.toString(arr));
}
Copy the code

The results

Input array:int[] arr = {4.6.8.5.9};
[4.9.8.5.6]
[9.4.8.5.6]
[9.6.8.5.4]
[4.6.8.5.9]
[8.6.4.5.9]
[5.6.4.8.9]
[6.5.4.8.9]
[4.5.6.8.9]
[5.4.6.8.9]
[4.5.6.8.9]
Copy the code

But following the steps above, at this point we can see that the result is consistent with the calculation, and at the end of the extra round, the demo will stop when the result is correct.