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

Today we are going to talk about a special kind of tree, called a Heap.

Ps: Please give me a thumbs up

The definition of the heap

  • A heap is a complete binary treeA complete binary tree is one in which all nodes must be full except for the lowest node, and all the lowest nodes are left
  • The current node of the heap must be greater than or equal to its children —The heap whose current node is greater than or equal to its children is called the big top heap, and the heap whose current node is less than or equal to its children is called the small top heap

The realization of the heap

Since the heap is a complete binary tree, we can easily store the heap using arrays (arrays start at 1 bit for easy counting).

How do I insert elements into the heap?

For example, if the number 5 is inserted into the big top heap above, we compare the nodes from bottom to top. If the nodes do not meet the rules of the big top heap, they switch, and if they meet, they break out of the loop

const Heap = function() {
    / / the current heap
    this.heap = [null.6.5.4.3.2.1];
    // The amount of data in the heap
    this.count = 6;
    this.add(5);
}

Heap.prototype.add = function(val) {
    this.heap.push(val);
    this.count++;
    heapifyUp(this.heap, this.count);
}

// Heap from bottom to top
const heapifyUp = function(heap, i) {
    while (i >> 1 > 0 && heap[i >> 1] < heap[i]) {
        swap(heap, i >> 1, i);
        i = i >> 1; }}const swap = function(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}
Copy the code

How do I delete data from the top of the heap

The top data is removed and the bottom data is placed on top of the heap, and the heap is heaped from top to bottom. Compare the current node with the left node to pick the lowest subscript, compare it with the right node to pick the lowest subscript, and then swap. If there is no node swap, break out of the loop, otherwise point to the smallest node and continue.

const Heap = function() {
    this.heap = [null.6.5.4.3.2.1];
    this.count = 6;
}

Heap.prototype.removeTop = function() {
    Swap the top and bottom of the heap
    swap(this.heap, 1.this.count);
    const topVal = this.heap.pop();
    this.count--;
    heapifyDown(this.heap, 1.this.count);
    return topVal;
}

const heapifyDown = function(heap, i, n) {
    while(true) {
        let posi = i;
        if (i * 2 <= n && heap[i * 2] > heap[i]) posi = i * 2;
        if (i * 2 + 1 <= n && heap[i * 2 + 1] > heap[posi]) posi = i * 2 + 1;
        if (i === posi) break; swap(heap, i, posi); i = posi; }}const swap = function(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}

const heap = new Heap();
heap.removeTop(); / / 6
heap.removeTop(); / / 5.Copy the code

How do I heap sort an array

Suppose you have an unordered array [2,3,6,4,5,1] that needs to be sorted in ascending order. You first need to build the heap and then sort it

There are two ways to build a heap:

  • One is similar to adding data, heap from bottom to bottom from the end of the array, because the time complexity of heap a node is O(logn), the top node does not need to sort, so the time complexity of this heap is (n-1) * O(logn) = O(nlogn).

  • The other option is the top-down solution, because top-down, all the leaves at the bottom don’t need to be heaped, the last non-leaf node is heaped down, so is the time order n/2 times O(logn) = O(nlogn)? No, because the heapiness of children is proportional to height, with the highest heapiness at the top and lowest at the bottom.

So the time is really order n.

Let’s sort the heap according to the second option:

/ / build the heap
const buildHeap = function(nums){
    nums.unshift(null);
    const n = nums.length;
    for (let i = n >> 1; i > 0; i--) {
        heapify(nums, n, i)
    }
    return nums;
}

/ / heap
const heapify = function(heap, n, i) {
    while(true) {
        let maxPos = i;
        if (i * 2 <= n && heap[i * 2] > heap[i]) maxPos = i * 2;
        if (i * 2 + 1 <= n && heap[i * 2 + 1] > heap[maxPos]) maxPos = i * 2 + 1;
        if (maxPos === i) break; swap(heap, maxPos, i); i = maxPos; }}/ / sorting
const sort = function(nums) {
    let n = nums.length;
    let heap = buildHeap(nums);
    while (len > 1) {
        swap(heap, 1, n);
        n--;
        heapify(heap, n, 1)}return heap.shift();
}


const swap = function(arr, a, b) {
    [arr[a], arr[b]] = [arr[b], arr[a]];
}
Copy the code

We don’t need to create any extra space when sorting, because we’re generating the big top heap, and the top of the heap is the maximum, so we swap it with the end of the array, then we heap the first n-1 heap, and then swap the top of the heap with the second to last heap, and that’s sorted.

The time of sorting is O(nlogn), so the total time of sorting is O(n) times O(nlogn)=O(nlogn).

Heap sort is an in place sort algorithm with a space complexity of O(1), because sort will swap places, so it is an unstable sort algorithm.