Binary heap

define

A binary heap is a complete binary tree and satisfies the condition that all nodes are ≥ (maximum heap) or ≤ (minimum heap) children.

The characteristics of

  • All nodes are ≥ (maximum heap) or ≤ (minimum heap) children

storage

Use arrays to store binary heaps, starting from the root node and storing the array in the order root, left child, and right child, as shown in the figure below

Using arrays to store binary heaps has the following characteristics:

Index, which can obtain the index of its child node

  • The index of the left child is2 * index + 1
  • The index of the right child is2 * index + 2

Index, which can obtain the index of its parent node

  • The index of the parent node is(index - 1) / 2

Binary heap operation

Self-tuning of binary heap

floating

If the nodes do not meet the requirements of the binary heap, the binary tree will automatically adjust its structure. Floating operation means that the nodes adjust their positions from bottom to top

  // Float up
  / * * * *@param {*} Arr: the physical underlying storage array */ of the binary heap
  // We use a loop structure here, or we can use recursion. Each recursion compares the child node with the parent node and swaps the positions of both
  shiftUp(arr) {
    let childIndex = arr.length - 1;
    let parentIndex = Math.floor((childIndex - 1) / 2);
    const temp = arr[childIndex];
    Float until the top of the heap or the parent node is no longer larger than the child node
    while(childIndex > 0 && arr[parentIndex] > temp) {
      // Overwrite the value of the child node to the parent node (i.e. the parent node moves down)
      arr[childIndex] = arr[parentIndex];
      // Update the index of the child node (that is, the child node and the parent node swap places)
      childIndex = parentIndex;
      // Update the index of the parent node. The next loop continues to compare the parent node
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
    // At the end of the loop, assign the value of the new node to the end node of the float operation;
    arr[childIndex] = temp;
  }
Copy the code

sinking

  // Sink operation
  / * * * *@param {*} arr 
   * @param {*}   : node to sink */
  shiftDown(arr, index) {
    let temp = arr[index];
    let parentIndex = index;
    let childIndex = 2 * parentIndex + 1;
    while (childIndex < arr.length) {
      // The parent node swaps with the left and right child nodes
      if (childIndex + 1 < arr.length && arr[childIndex + 1] < arr[childIndex]) {
        // If the right node is smaller, make childIndex point to the right node
        childIndex ++;
      }
      if (temp < arr[childIndex]) {
        // The parent node is smaller than the child node and exits the loop without swapping
        break;
      }
      arr[parentIndex] = arr[childIndex];
      parentIndex = childIndex;
      childIndex = 2 * parentIndex + 1;
    }
    arr[parentIndex] = temp;
  }
Copy the code

Insert the node

The operation of inserting a node can be seen as inserting a new node as a leaf node and then ‘floating’ the binary heap itself.

  // Insert node in order (log(n)), where n is the capacity of binary heap (node tree)
  // Since the insert operation floats one layer at a time, the maximum number of possible floats for a binary heap of capacity N is log(n).
  / * * * *@param {*} Arr: The physical underlying storage array * of the binary heap@param {*} Node: The new node to be inserted, the value of which is node */
  insert(arr, node) {
    arr.push(node);
    this.shiftUp(arr);
  }
Copy the code

Remove nodes

Delete a node, that is, the top node of the binary heap is removed by replacing the top node with the last node of the heap and then sinking

  // Delete the node from the top of the heap in order (log(n))
  / * * * *@param {*} Arr: binary heap, where arrays are used to implement physical storage */
  pop(arr) {
    let res = this.arr[0];
    this.arr[0] = this.arr.pop();
    this.shiftDown(this.arr, 0);
    return res;
  }
Copy the code

Build a binary heap

There are two ways to construct an unordered number fabric into a binary heap

Insert the elements of the unordered array into the binary heap in turn

constructor(array) {
    this.arr = [];
    for(let i = 0; i < array.length; i ++) {
      this.insert(this.arr, array[i]); }}Copy the code
Time complexity analysis

The time complexity in this way is O(nlog(n)), which can be deduced as follows:

The maximum number of switches is the same for nodes in the same layer, and the leaf node in the last layer does not need to perform the switch because there are no nodes underneath it. The time complexity is O(sum(number of switches)) = O(number of nodes at each layer x maximum number of switches on nodes at this layer).

The number of binary heap layers of n nodes is k = log(n)

S = 0 + 1 + 1 + 2 + 2 + 2 + 2 + ... + k + k + ... + k; (2 1's, 4 2's,.... S = k * 2^k - 2^(k-1) + 2; S = nlog of n minus n over 2 plus 2;Copy the code

Think of an unordered array as an irregular binary heap, descending from the last non-leaf node

constructor(array) {
  this.arr = array;
  for(let i = Math.floor((this.arr.length - 1) / 2); i >=0; i --) {
    this.shiftDown(this.arr, i); }}Copy the code
Time complexity analysis

The time complexity in this way is O(n), which can be deduced as follows:

The maximum number of switches is the same for nodes in the same layer, and the leaf node in the last layer does not need to perform the switch because there are no nodes underneath it. The time complexity is O(sum(number of switches)) = O(number of nodes at each layer x maximum number of switches on nodes at this layer). The number of binary heap layers of n nodes is k = log(n), the number of nodes dSum of layer D and layer D meets the number of nodes dSum = 2 ^ (d-1), the maximum switching times of nodes of layer D is log(k-d), so the total switching times satisfies the following formula:

S = 2^0 * (k - 1) + 2^1 * (k -2) +... +2^(k-2) * [k- (k - 1)];
2S =                2^1 * (k - 1)+ ... + 2^(k-2) * [k - (k - 2)] + 2^(k-1) * [k - (k - 1)]; Subtract these two and you get S is equal to2^k - k - 1; And since k is log of n, S is n minus log of n minus1;
Copy the code

So the time complexity is O(S) = O(n);

The two ways are whether it changes the array passed in.

Application of binary heap

  • Find the maximum or minimum value quickly and efficiently (time complexity O(1))
  • Find the KTH largest (small) element (build a binary heap, node tree k (heap size K))
  • Find the first K largest (small) elements (build a binary heap, node tree k (heap size K))

Find the KTH largest element (see LeetCode 215)

  • Build a minimum heap of size K and insert the elements into the heap in turn
  • When the size of the heap exceeds K, the top of the heap is removed, leaving the size of the heap unchanged
  • When all elements are inserted, the top element is the KTH largest element

Find the first K high frequency elements (see LeetCode 347)

Priority queue

define

  • Maximum priority queue: Queue is no longer fifO, regardless of the queue status, the element with the largest value is first out of the queue
  • Minimum priority queue: Queues are no longer fifO, and the element with the smallest value gets out first, regardless of the queue status

implementation

The maximum (small) priority queue can be implemented using the maximum (small) heap.

// Maximum priority queue, using maximum heap
class PriorityQueue {
  / * * * *@param {*} N: Queue length */
  constructor (n) {
    this.arr = [];
    this.size = n;
  }
  enQueue(element) {
    this.insert(this.arr, element);
    if (this.arr.length > this.size) {
      this.size ++; }}deQueue() {
    if (this.arr.length === 0) {
      throw new Error('no element! ');
    }
    return this.pop(); }}Copy the code