What is a heap?

The heap is a complete binary tree data structure!

The average queue Priority queue (heap)
Queue up from the beginning From the pop-up
Enter the queue from the tail From the tail insertion
First in first out Weight per queue (Max/min)
Array implementation Array implementation (data structure viewed as heap)
Bunch of useless
  • 703. The k-th large element in the data stream
  • Heap sort
How is the heap implemented?

The previously implemented minimum heap can be looked back

First we need to find the relationship between the left and right children and their parents.

The following figure shows the index diagram of each child node when the root node is index 0

ParentIndex = parentIndex
leftIndex = parentIndex * 2 + 1
rightIndex = parentIndex * 2 + 2

// Find the parent node of the child nodeParentIndex = (childIndex -1) > >1 // If I round left and right, I get the same result
Copy the code

We then build the heap based on node relationships (typically using the big top heap)

class Heap{
    constructor(){
        this.data = [] // Initialize array storage
        this.cnt = 0 / / the length
    }
    //  
    size(){
        return this.cnt 
    }
    // Top element
    top(){
        if(this.size()==0)return -1
        return this.data[0]}swap(i,j){[this.data[i], this.data[j]] =[this.data[j], this.data[i]]
    }
    // Insert elements
    push(val){
        this.data[this.cnt ++] = val
        this.liftUp(this.cnt-1) // Adjust upward
    }
    // 
    liftUp(ind){
        // Compare with the parent node. If it is larger than the parent node, swap with the parent node
        let parentIndex = (ind - 1) > >1
        while(ind && this.data[ind] > this.data[parentIndex]){
            parentIndex = (ind - 1) > >1
            this.swap(ind, parentIndex)
            ind = parentIndex
        }
    }
    // Pop up elements
    pop(){
        this.data[0] = this.data.pop()  // Place the last element in the head to adjust downward
        // If you need heap sort, change the above code directly
        // this.swap(0, cnt-1)
        this.cnt -=1
        this.liftDown(0)}liftDown(ind){
        // If it is smaller than the child node, adjust it downward
        let n = this.cnt - 1
        while(leftChildIndex <= n){
            let temp = ind
            let leftChildIndex = ind * 2 + 1
            let rightChildIndex = ind * 2 + 2
            if(this.data[ind] < this.data[leftChildIndex] ) temp = leftChildIndex// leftChildIndex<=n indicates a left child node
            if(rightIndex<=n && this.data[ind]< this.data[rightChildIndex]) temp = rightChildIndex // rightChildIndex<=n indicates a right child node
            if(temp == ind) break ; // No adjustment is required
            this.swap(ind ,temp) // Swaps need to be adjusted
            ind = temp
        }
    }
}


Copy the code