This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Binary heap and heap sort

Today we’re going to learn about a special binary tree, our heap data structure, also known as a binary heap, which is efficient and fast at finding minima and maxima, and is often used in priority queues and heap sorting algorithms.

This section covers binary heap data structures, Max and min heaps, and heap sorting algorithms.

Binary heap data structures

Binary heap is a special binary tree with the following two characteristics:

  1. It is a complete binary tree, meaning that each layer of the tree has left and right child nodes (except the leaf node of the last layer), and the leaf node of the last layer should be left node as much as possible, which is called structural property
  2. A binary heap is either a minimum heap or a maximum heap, and the minimum heap allows you to quickly find the minimum of the tree, and the maximum heap allows you to quickly find the maximum of the tree. All nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) each of its children, which is called heap property.

Implement minimum heap

To define our heap’s data structure, we also need the compareFn function to compare the values of two numbers and the heap attribute to store our heap elements.

const defaultCompare = (a, b) => a > b class MinHeap { constructor(compareFn = defaultCompare) { this.heap = []; this.compareFn = compareFn; }}Copy the code

Here we use an array to represent the binary heap. The value of the parent node, the left and right child nodes is detected by the index value. For a node given index, the index of the left child node is 2 * index + 1, and the index of the right child node is 2 * index + 2. The parent node is math.floor ((index-1) / 2), so we can get the following function.

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

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

getParentIndex(index) {
    if (index === 0) {
        return undefined
    }
    return Math.floor((index - 1) / 2)
}
Copy the code

Let’s look at some of the basic approaches needed to implement a minimal heap

  • Insert (value) : Like inserting a value into the heap, return true on success, false otherwise
  • Extract () : Removes the minimum (minimum heap) or maximum (maximum heap) value and returns that value
  • FindMininum () : Returns either a minimum (minimum heap) or a maximum (maximum heap) without removing the value

insert

Implementation steps:

  1. Return false if value is invalid; Insert it to the end of the array if it’s legal, and then move it up
  2. The newly inserted value (the last value in the array) is compared to its parent, and if it is smaller than the parent, the two are swapped and the cycle continues until the parent or index exceeds the array index. The concrete implementation is as follows:
Insert (value) {// value is valid when inserted, otherwise insert failed false if (value! = null) {this.heap.push(value); This.siftup (this.heap.length - 1) return true; } return false} siftUp(index) {let parent = this.getparentIndex (index); // while(index > 0 && this.heap[parent] > this.heap[index]) { while (index > 0 && this.compareFn(this.heap[parent], this.heap[index])) { [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]] index = parent; parent = this.getParentIndex(index); }}Copy the code

Let me write an example to test it

const minHeap = new MinHeap()
minHeap.insert(2)
minHeap.insert(3)
minHeap.insert(4)
minHeap.insert(5)

minHeap.insert(1)

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

findMininum

In the minimal heap, the minimum value is always the first value in the array, so the function is implemented as follows:

size() {
    return this.heap.length;
}
isEmpty() {
    return this.size() === 0
}

findMininum() {
    // 或者直接返回 this.heap[0];
    return this.isEmpty() ? undefined : this.heap[0];
}
Copy the code

extract()

The extract() function is used to remove the minimum (minimum heap) or maximum (maximum heap) and return the value. And that’s what we’re going to do.

Implementation steps:

  1. Return undefined if the heap is empty; If there is only one element, delete the first element and return
  2. When there are multiple elements, delete the first element and return, then move down to rebuild the minimal heap
  3. After removing the smallest element, compare the first element as the top of the heap and its children
  4. Compare the left and right nodes, find the smallest value that is smaller than them, and then swap,
  5. Step 2 of loop
extract() {
    if (this.isEmpty()) return undefined;
    if (this.size() === 1) return this.heap.shift();

    const removeVal = this.heap.shift();
    this.siftDown(0);
    return removeVal;
}

siftDown(index) {
    let element = index;
    const left = this.getLeftIndex(index)
    const right = this.getRightIndex(index);
    const size = this.size()

    if (left < size && this.compareFn(this.heap[element], this.heap[left])) {
        element = left;
    }

    if (right < size && this.compareFn(this.heap[element], this.heap[right])) {
        element = right;
    }

    if (index !== element) {
        [this.heap[index], this.heap[element]] = [this.heap[element], this.heap[index]]
        this.siftDown(element);
    }
}
Copy the code

Implement maximum heap

The algorithm for the maximum heap and the minimum heap is exactly the same, except that you replace all the greater than with less than comparisons.

const reverseCompare = compareFn => (a, b) => compareFn(b, a) class MaxHeap extends MinHeap { constructor(compareFn) { super(compareFn); this.compareFn = reverseCompare(compareFn); }}Copy the code

The test case

const maxHeap = new MaxHeap() maxHeap.insert(2) maxHeap.insert(3) maxHeap.insert(4) maxHeap.insert(5) maxHeap.insert(1) console.log(maxHeap); // { heap: [ 5, 4, 3, 2, 1 ] console.log(maxHeap.findMininum()); / / 5Copy the code