Mp.weixin.qq.com/s?__biz=MzI…

In the last comic, Xiao Hui introduced binary heap as a powerful data structure:

 

Comics: What is a binary heap? (Revised version)

 

So, how does this binary heap work? We’ll talk more about that in this issue.

 

 

 

 

 

 

Let’s review the properties of binary heap and maximum heap:

 

1. Binary heap is essentially a complete binary tree

2. The top of the largest heap is the largest element in the heap ****

 

When we remove the top of the largest heap (not completely, but at the very end), the second largest element is self-adjusted to become the new top of the largest heap.

 

 

 

As shown in the figure above, when we remove the top node of the heap with a value of 10, we adjust it to replace it with a value of 9. When we remove the top node of the heap with a value of 9, the new node of the heap with a value of 8 is adjusted to replace…….

 

Because of this property of binary heaps, each time we remove the old top, the new top is adjusted to be the node next in size to the old top. So as long as we repeatedly delete the top of the heap and adjust the binary heap, the set obtained becomes an ordered set, and the process is as follows:

 

 

Delete node 9 and node 8 becomes the new heap top:

 

 

 

Delete node 8 and node 7 becomes the new heap top:

 

 

 

Delete node 7 and node 6 becomes the new heap top:

 

 

 

Delete node 6 and node 5 becomes the new heap top:

 

 

 

Delete node 5 and node 4 becomes the new heap top:

 

 

 

Delete node 4 and node 3 becomes the new heap top:

 

 

 

Delete node 3 and node 2 becomes the new heap top:

 

 

 

So at this point, what was originally our largest heap has become an ordered set from small to large. As mentioned earlier, the binary heap is actually stored in an array of elements arranged as follows:

 

 

 

From this, we can summarize the steps of heap sort algorithm:

 

1. Construct disordered number fabric into binary heap.

2. Loop to remove the top of the heap, move to the end of the collection, adjust the heap to generate a new top.

 

 

 

 

 

 

public class HeapSort {

 
Copy the code

  1. / * *

  2. * Sinking adjustment

  3. * @param array Specifies the heap to be adjusted

  4. * @param parentIndex The parent node to sink

  5. * @param parentIndex The effective size of the heap

  6. * /

  7. public static void downAdjust(int[] array, int parentIndex, int length) {

  8. // temp holds the parent value for the final assignment

  9.    int temp = array[parentIndex];

  10.    int childIndex = 2 * parentIndex + 1;

  11.    while (childIndex < length) {

  12. // If there is a right child and the value of the right child is greater than the value of the left child, locate the right child

  13.        if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {

  14.            childIndex++;

  15.        }

  16. // If the parent node is smaller than any of the children, jump out

  17.        if (temp >= array[childIndex])

  18.            break;

  19. // No real exchange, one-way assignment

  20.        array[parentIndex] = array[childIndex];

  21.        parentIndex = childIndex;

  22.        childIndex = 2 * childIndex + 1;

  23.    }

  24.    array[parentIndex] = temp;

  25. }

  26.  

  27.  

  28. / * *

  29. * heap sort

  30. * @param array Specifies the heap to be adjusted

  31. * /

  32. public static void heapSort(int[] array) {

  33. // 1. Unordered number fabric into binary heap.

       for (int i = (array.length-2)/ 2; i >= 0; i--) {

  34.        downAdjust(array, i, array.length);

  35.    }

  36.    System.out.println(Arrays.toString(array));

  37. // 2. Loop to remove the heap top element, move to the end of the collection, adjust the heap to create a new heap top.

  38.    for (int i = array.length - 1; i > 0; i--) {

  39. // The last element swaps with the first element

  40.        int temp = array[i];

  41.        array[i] = array[0];

  42.        array[0] = temp;

  43. // Sink to adjust maximum heap

  44.        downAdjust(array, 0, i);

  45.    }

  46. }

  47.  

  48.  

  49. public static void main(String[] args) {

  50. Int [] arr = new int[] {1,3,2,6,5,7,8,9,10,0};

  51.    heapSort(arr);

  52.    System.out.println(Arrays.toString(arr));

  53. }

}

 

 

 

 

 

The downAdjust method of binary heap is the basis of heap sorting algorithm. What is the time complexity of this adjustment operation itself?

 

Assuming a total of n elements in the binary heap, the worst time complexity of the sink adjustment is the same as the height of the binary heap, which is O (logn).

 

Let’s review the steps of heapsort again:

 

1. Construct disordered number fabric into binary heap.

2. Loop to remove the top of the heap, move to the end of the collection, adjust the heap to generate a new top.

 

In the first step, the disordered number fabric is constructed into a binary heap, which requires N /2 cycles. DownAdjust is called once per cycle, so the scale of the first step is n/2 * logn and the time complexity is O (nlogn).

 

The second step requires n-1 cycles. DownAdjust is called once per cycle, so the size of the second step is (n-1) * logn, and the time complexity is O (nlogn).

 

The two steps are parallel, so the overall time complexity is also O (nlogn).

 

 

 

 

 

 

 

 

 

 

 

 

 

— — the END — — –