Sword finger offer II 076 The kth largest number in the array (use heap to solve TOPK problem)

The finger of the sword Offer II 076. The... In the array k Big numbers （ Use the heap to solve topK problem ）

Title Description

Their thinking

This question is a very basic and classic topK problem . Take this opportunity to , By the way, sort out the writing of heap sorting .

The first is to adjust the structure of the heap and the code for building the heap , Take the big top pile for example ：

// Adjust the structure of the heap so that the root node is greater than or equal to its child node 
void maxHeapify(vector<int>& a, int i, int heapSize) {
    
    int left = i * 2 + 1, right = i * 2 + 2;	// Complete binary tree subscript is i The subscript of the left and right child nodes of the node 
    int largest = i;	// Suppose that the root node and the largest of the left and right children are roots 
    // Find the root node and the maximum value in the left and right children 
    if (left < heapSize && a[left] > a[largest]) {
    
        largest = left;
    }
    if (right < heapSize && a[right] > a[largest]) {
    
        largest = right;
    }
    //  If the following node is not the maximum value , Adjust the structure of the heap 
    if (largest != i) {
    
        swap(a[i], a[largest]);	// Make the maximum value the following node 
        maxHeapify(a, largest, heapSize);	// Continue to recursively adjust downward 
    }
}
// Start building the heap from the last non leaf node 
void buildMaxHeap(vector<int>& a) {
    
    // Starting from the last non leaf node of the complete binary tree 
    for (int i = a.size() / 2 - 1; i >= 0; i--) {
    	
        maxHeapify(a, i, a.size());
    }
    // Heap sort ： After the reactor is built , You also need to traverse backwards from the end of the array , Continue to adjust the structure of the heap 
    for (int i = a.size() - 1; i >= 1; i--) {
    
        swap(a[i], a[0]);
        maxHeapify(a, 0, i);
    }
}

What needs to be explained is buildMaxHeap() function . When the reactor building is completed , The elements in the heap satisfy “ The root node is greater than or equal to its child node ” This principle , however , The elements of each layer are not necessarily orderly , That is to say, the elements in the array are still in a partially ordered state , If you want to get an ordered array, you need to continue to adjust . As shown in the code above , From the end of the array n - 1 Traversing the array backwards , Put the last element a[n - 1] With the top element a[0] In exchange for , Then adjust a[0] To a[n - 2] The structure of the heap in scope （ The elements at the end have been ordered , There is no need to adjust ）, So the element at the end of the array is the largest . And so on , Finally, we get a non decreasing ordered array .

For such topK problem , If the heap size is k , Then the elements in the heap need not be completely ordered , Just make sure that the top element is this k The largest of the elements （ Or the smallest ） The can , Therefore, it is not necessary to completely adjust to an orderly state . That is the solution to this problem , Use a size of k The little top pile , The code is as follows ：

// Adjust the structure of the heap so that the root node is less than or equal to its child node 
void minHeapify(vector<int>& a, int i, int heapSize) {
    
    int left = i * 2 + 1, right = i * 2 + 2;
    int minIndex = i;
    if (left < heapSize && a[left] < a[minIndex]) {
    
        minIndex = left;
    }
    if (right < heapSize && a[right] < a[minIndex]) {
    
        minIndex = right;
    }
    if (minIndex != i) {
    
        swap(a[minIndex], a[i]);
        minHeapify(a, minIndex, heapSize);
    }
}
// Start building the heap from the last non leaf node , Note that the heap size is no longer an array a Size , It's defined heapSize
void buildMinHeap(vector<int>& a, int heapSize) {
    
    // First use the first... In the array heapSize Build a pile of numbers 
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
    
        minHeapify(a, i, heapSize);
    }
    // Then traverse the remaining elements in the array , If it is greater than or equal to the heap top element , Just swap with the top of the heap element , Adjust the structure of the heap 
    for (int i = heapSize; i <= 1; i++) {
    
        if (a[i] >= a[0]) {
    
            swap(a[i], a[0]);
            minHeapify(a, 0, heapSize);
        }
    }
    // After traversal , The elements in the heap are the front k The biggest element , The top of the heap element is the second k Big elements 
}

int findKthLargest(vector<int>& nums, int k) {
    
    buildMinHeap(nums, k);
    return nums[0];
}