Their thinking

The whole heap sorting process can be summarized as: up and down

Why do I need a heap to solve this problem?

A lot of you might think of a solution like, let me sort the whole array, so I can get the KTH largest element, so that’s one way to do it, but we need the KTH largest element, so we don’t have to sort all of them, we just sort some of them, and that’s obviously less complicated

To solve this problem, use heap sort — create a large heap, and after k−1 deletion, the top elements of the heap are the answers we are looking for.

Heap sort

Basic introduction

Heap sort is a kind of sorting algorithm designed by using heap data structure, it is a kind of selective sorting, the worst, the best, the average time complexity is O(nlogn), it is unstable sorting.

Note that because of the nature of binary trees, you can use an array to represent the corresponding tree structure. This is called sequential storage

Sequential storage of binary trees

The characteristics of

  • The left child of the NTH element is 2 times n plus 1
  • The right child of the NTH element is 2 times n plus 2
  • The parent of the NTH element is (n-1)/2
  • The last non-leaf node is math.floor (arr.length/2)-1

A heap is a complete binary tree with the following properties:

  • Big top heap: Each node has a value greater than or equal to the value of its left and right children

    Note: No size relationship between left and right values is required

  • Small top heap: Each node has a value less than or equal to the value of its left and right children

For example:

The big top heap is an example

Nodes in the heap are numbered by layer and mapped into an array as shown below

Big top heap features: ARr [I] >= ARr [2* I +1] && arr[I] >= ARr [2* I +2], I corresponds to the number of nodes, I is numbered from 0

Small top heap example

Small top heap characteristics: ARr [I] <= ARr [2* I +1] && arr[I] <= arr[2* I +2], I corresponds to the number of nodes, I starts from 0

Ordering instructions

  • Ascending: Large top heap is generally used
  • Descending order: Small top heap is generally used

The basic idea

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

    Note: This is an array, not a binary tree

  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, so that the subsmallest values of n elements are obtained. So again and again, you get an ordered sequence.

Diagram of heap sorting steps

Heap sort on arrays 4,6,8,5,9, sort the array upward.

Step 1: Construct the initial heap

  1. Given the unordered sequence structure as follows: Note that the operations here use arrays, and the tree structure is just for reference

Construct the given unordered sequence into a large top heap.

  1. At this point, adjust from the last non-leaf node, left to right, and top to bottom.

The leaf node does not need to be adjusted. The first non-leaf node arr.length/2-1 = 5/2-1 = 1, that is, the node with element 6.

Comparison: first compare 5 with 9 to get the largest one, and then compare with 6 to find that 9 is greater than 6, then adjust their position.Copy the code

  1. Find the second non-leaf node 4 due to,9,8 [4]Where, element 9 is the largest, then 4 and 9 are exchanged

  1. At this point, the interchange results in child roots(4 and 6)The structure is chaotic, and it continues to be adjusted.(4 and 6)Medium 6 is the largest, adjust 4 and 6.

At this point, an unordered sequence is constructed into a large top heap.

Step 2: Swap the top and bottom elements of the heap

Swap the top element of the heap with the last element to make the last element the largest. We then continue to adjust and swap 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 subsequent process of adjustment, exchange, and so on and so on, and finally the sequence is in order

Summarizes the train of thought

  1. The unordered sequence is constructed into a heap, and the large top heap is selected according to the ascending and descending requirements
  2. Swap the top element with the end element, “sinking” 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 and current end elements, repeating the adjustment and swap steps until the sequence is in order.

steps

A few points to note here (key ideas for code implementation) :

  1. The first step is to build the initial heap: it is built bottom-up, starting with the last non-leaf node.

  2. The second step is a sink operation that swaps the tail element with the top element, puts the maximum value at the end of the array, and reduces the length of the array and does not participate in the subsequent adjustment of the top heap

  3. The third step is readjustment: top to bottom, left to right, as the top element sinks to the end. Readjustment of the big top heap

The code template

I refer to the official code template, which is easier to remember than some books, so you can refer to it as a heap sort template

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
 // The whole process is up and down
var findKthLargest = function(nums, k) {
   let heapSize=nums.length
    buildMaxHeap(nums,heapSize) // Build a big top heap
    The big top heap is the largest element to sink to the end
    for(let i=nums.length-1; i>=nums.length-k+1; i--){ swap(nums,0,i)
        --heapSize // Sunk elements do not participate in the adjustment of the big top heap
        // Readjust the big top heap
         maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
   // Build a big top heap from the bottom up
   function buildMaxHeap(nums,heapSize){
     for(let i=Math.floor(heapSize/2) -1; i>=0; i--){ maxHeapify(nums,i,heapSize) } }// Adjust nodes from left to right, top-down
   function maxHeapify(nums,i,heapSize){
       let l=i*2+1
       let r=i*2+2
       let largest=i
       if(l < heapSize && nums[l] > nums[largest]){
           largest=l
       }
       if(r < heapSize && nums[r] > nums[largest]){
           largest=r
       }
       if(largest! ==i){ swap(nums,i,largest)// Adjust the node
           // Continue to adjust the non-leaf nodes below
           maxHeapify(nums,largest,heapSize)
       }
   }
   function swap(a, i, j){
        lettemp = a[i]; a[i] = a[j]; a[j] = temp; }};Copy the code

Heap sort

findKthLargest(nums,nums.length)
// let I =nums.length-1; i>=nums.length-k+1; On the condition that
Copy the code