“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

The idea of this algorithm comes from the KTH largest number in the data stream. So the traditional way of thinking about it is, you go through as many as you have, sort them, and then you take the KTH largest number at k minus 1. Such time complexity is high.

I just need the KTH name, and that’s not necessary for us to get the KTH name. Is there any way we can reduce the complexity?

At this point we need to implement a minimum heap. The minimal heap maintains a complete binary tree.

Complete binary tree: Let the depth of the binary tree be H, except for the h layer, the number of nodes of all other layers (1-H-1) reaches the maximum, and all nodes of the H layer are continuously concentrated on the left

Implementation method

LeftIndex = (parentIndex + 1) * 2-1 rightIndex = leftIndex + 1 */
class MinHeap{
    constructor(data = []){
        this.data = data
    }
    // Get the minimum value
    peek (){
        return this.size() == 0 ? null : this.data[0]}/ / to compare
    compare(a , b){
        return a-b
    }
    // Switch places
    swap(i, j){[this.data[i] , this.data[j]] = [this.data[j] , this.data[i]]
    }
    
    push(node){
        this.data.push(node)
        siftUp(node, this.size() -1)}// Adjust upward
    siftUp(node ,i){
        let index = i;
        while(index > 0) {let parentIndex = (index - 1) > >1
            let parent = this.data[parentIndex]
            // The child node is smaller than the parent node
            if(this.compare(node , parent) < 0) {this.swap(parentIndex, index)
                index = parentIndex
            }else{
                break; }}}// Delete elements
    pop(){
        if(this.size() == 0) {return null
        }
        const last = this.data.pop()
        if(this.size() ! =0) {this.data[0] = last
            siftDown(last, 0)}}// Adjust downward
    siftDown(node ,i){
        let index = i
        const len = this.size()
        const halfLength = len >> 1
        while(index < halfLength){
            let leftIndex = (index + 1) * 2 -1
            let rightIndex = leftIndex +1
            
            let left = this.data[leftIndex]
            let right = this.data[rightIndex]
            // left is less than parent
            if(this.compare(left , node) < 0) {/ / right is minimal
                if(rightIndex < len && this.compare(right , node) < 0) {this.swap(rightIndex, index)
                    index = rightIndex
                }else{
                 / / left is minimal
                    this.swap(leftIndex, index)
                    index = leftIndex
                }
            }else if(rightIndex < len && this.compare(right , node) < 0) {// Left is greater than parent and right is smaller than parent
                this.swap(rightIndex, index)
                index = rightIndex      
            }else{
                // The gift is the minimum root node
                break; }}}size(){
        return this.data.length
    }
}
Copy the code

And that’s the end of the smallest heap.

How do we calculate the number one in the data streamkWhat about the big numbers?
 const KLargest = (k , nums) = > {
     this.k = k
     this.heap = new MinHeap()
     for(const num of nums){
         this.add(num)
     }
 }
 KLargest.prototype.add = function(node){
     / / add
     this.heap.push(node)
     // If the heap exceeds k, add and delete
     if(this.heap.size() > this.k){
         this.heap.pop()
     }
     // Returns the smallest element
     return this.heap.peek()
 }
Copy the code