Front-end data structure (7) stack

This is the eighth day of my participation in the August Gwen Challenge.

Data structure (6) diagram of the front end

Today’s chapter introduces the data structure heap.

The heap

Heap is a special kind of complete binary tree.
All nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) its children.

JS in the heap

JSThe heap is usually represented by an array.

All the binary trees we talked about before are represented by Object, how can we use an array here?

As shown in figure:

We can use the breadth-first traversal order as the array subscript, and the traversal value as the array value, so we can represent a heap.

The position of the left child node is 2 index + 1.
The position of the child node on the right is 2 index + 2.
The parent position is (index-1) / 2.

The application of the heap

The heap can find the maximum and minimum values efficiently and quickly, time complexity: O(1).
Find the KTH largest (small) element.

How do you find the KTH largest element?

Build a minimal heap and insert the elements in sequence into the heap.
When the heap size exceeds K, the heap top is removed.
After insertion, the top of the heap is the KTH largest element.

First let’s implement a minimal heap class

The statement

In a class, declare an array to hold elements.

class MinHeap {
    constructor() {
        this.heap= []}}Copy the code

Main implementation methods

Main methods: insert, delete heap top, get heap top, get heap size.

insert

Insert the value at the bottom of the heap, at the end of the array.
Then move up: swap the value with its parent until the parent is less than or equal to the inserted value.
The time complexity of inserting elements into the heap of size K is O (logk)

class MinHeap {
    constructor() {
        this.heap = []
    }

    swap(i1, i2) {
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }

    getParentIndex(i) {
        // Write it like this
        // Math.floor((i - 1) / 2)
        // Move forward one bit by binary
        // implement the division of 2 integer
        return (i - 1) > >1
    }

    shiftUp(index) {
        if (index === 0) return
        const parentIndex = this.getParentIndex(index)
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index)
            this.shiftUp(parentIndex)
        }

    }

    insert(value) {
        this.heap.push(value)
        this.shiftUp(this.heap.length - 1)}}const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)

console.log(h);
// MinHeap { heap: [ 1, 3, 2 ] }
Copy the code

While not incrementing like an array, the top of the heap is guaranteed to be smaller than the nodes that follow.

Delete the pile top

Replace the top of the heap with an element at the end of the array (removing the top directly breaks the heap structure).
Then move down: swap the new heap top with its children until the children are greater than or equal to the new heap top.
The time complexity for removing the top of a heap of size K is O (logk).

class MinHeap {
    constructor() {
        this.heap = []
    }

    swap(i1, i2) {
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }

    getLeftIndex(i) {
        return i * 2 + 1
    }

    getRightIndex(i) {
        return i * 2 + 2
    }

    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRightIndex(index)
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, rightIndex)
            this.shiftDown(leftIndex)
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, rightIndex)
            this.shiftDown(rightIndex)
        }
    }

    pop() {
        this.heap[0] = this.heap.pop(a)this.shiftDown(0)}}const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)
h.pop()

console.log(h)
// MinHeap { heap: [ 2, 3 ] }

Copy the code

Gets the top and size of the heap

Get the top of the heap: Returns the head of the array.
Get the heap size: Returns the length of the array.

class MinHeap {
    constructor() {
        this.heap = []
    }

    peek() {
        return this.heap[0]
    }

    size() {
        return this.heap.length}}const h = new MinHeap()
h.insert(3)
h.insert(2)
h.insert(1)

console.log(h);
/ / 1 3
Copy the code

End~~~