The previous article “TypeScript Data Structures and Algorithms: Red-black Trees” implemented the self-balancing red-black tree data structures and algorithms in TypeScript. This article continues to implement binary Heap.

Binary heap

Binary heap is a special binary tree that can efficiently and quickly find maximum and minimum values. It is often used in priority queues and is also used in famous heap sorting algorithms. It has two characteristics:

  • The structural characteristics: It’s a treeComplete binary tree, means that every layer of the tree has left and right child nodes (except the leaf node of the last layer), and the leaf nodes of the last layer are all left child nodes as far as possible.
  • Heap featuresBinary heap is either the smallest heap or the largest heap. The minimum heap allows you to quickly extract the minimum value of the tree, and the maximum heap allows you to quickly extract the maximum value 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.

A complete binary tree satisfying heap order is shown in the following figure:

Binary heap representation

In the previous representation of binary tree data structure, the use of special tree data structure, by reference to the left and right child nodes. But since the binary heap is a complete binary tree, it can be implemented using a simpler array structure, as shown in the figure below. The parent node of the node at position K is at ⌊k/2⌋, while its two children are at 2k and 2K +1, respectively. So you can move up and down the tree by counting the index of the array: one level up from a[k] makes k equal to k/2, and one level down makes k equal to 2k or 2K +1.

Data structure implementation

Switching elements

We’ll start with a helper method that swaps two elements in an array using ES6’s destruct assignment:

/ * * *@description: Swaps the value */ at two positions in the array
export function swap(array: any[], a: number, b: number) {
  [array[a], array[b]] = [array[b], array[a]];
}
Copy the code

Binary heap class

Implement a minimum binary heap MinHeap class. The maximum heap is similar, just invert the comparison function into reverseCompare.

Some basic methods are implemented in the class, such as getting the left child node, right child node and parent node index methods:

import {
  Compare,
  defaultCompare,
  ICompareFunction,
  reverseCompare,
  swap
} from ".. /util";

// Minimum heap class
export class MinHeap<T> {
  protected heap: T[] = [];

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {}

  / * * *@description: Gets the index of the left child node */
  private getLeftIndex(index: number) :number {
    return 2 * index + 1;
  }

  / * * *@description: Gets the index */ of the child node on the right
  private getRightIndex(index: number) :number {
    return 2 * index + 2;
  }

  / * * *@description: Gets the index of the parent node */
  private getParentIndex(index: number) :number {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  / * * *@description: Returns the length of the heap array */
  size(): number {
    return this.heap.length;
  }

  / * * *@descriptionReturns whether the heap is empty */
  isEmpty(): boolean {
    return this.size() <= 0;
  }

  / * * *@descriptionEmpty the heap */
  clear() {
    this.heap = [];
  }

  / * * *@description: returns the heap top value */
  findMinimum(): T {
    return this.isEmpty() ? undefined : this.heap[0];
  }

  / * * *@description: returns the array that holds binary heap data */
  getAsArray() {
    return this.heap; }}// Reverse the compareFn result
export class MaxHeap<T> extends MinHeap<T> {
  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
    super(compareFn);
    this.compareFn = reverseCompare(compareFn); }}Copy the code

floating

If a node in the heap becomes larger than the parent due to some operation, then we need to fix the heap by swapping it with the parent. If the swap is still larger than the grandfather node, the swap continues until the heap’s ordered state is restored. As shown below:

The implementation code for the float is as follows:

  / * * *@description: recursive method of moving up */
  private siftUp(index: number) :void {
    // The core of the implementation is to keep swapping to the parent node until the appropriate location
    let parent = this.getParentIndex(index);
    while (
      index > 0 &&
      this.compareFn(this.heap[parent], this.heap[index]) ===
        Compare.BIGGER_THAN
    ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index); }}Copy the code

sinking

Similarly, if a node in the heap becomes smaller than its children due to some operation, then we need to fix the heap by swapping it with its children. If the swap is still smaller than the grandchild, the swap continues until the heap’s ordered state is restored.

However, the sinking operation is a little more complicated, you can choose to sink left or right, after all, the binary heap is a completely left-leaning binary tree, so the principle is to sink as far as possible to the left, not to sink left and then sink right. As shown below:

The implementation code for sinking is as follows:

  / * * *@description: recursive method of moving down */
  private siftDown(index: number) {
    let element = index;
    // The move down method is a bit more complicated, because the move down should be left or right
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();

    // First move left and down
    if (
      left < size &&
      this.compareFn(this.heap[element], this.heap[left]) ===
        Compare.BIGGER_THAN
    ) {
      element = left;
    }

    // Next move down to the right
    if (
      right < size &&
      this.compareFn(this.heap[element], this.heap[right]) ===
        Compare.BIGGER_THAN
    ) {
      element = right;
    }

    / / exchange
    if(index ! == element) { swap(this.heap, index, element);
      // Continue the recursion
      this.siftDown(element); }}Copy the code

Insert and delete elements

So, once we’ve talked about up and down, what exactly causes a binary heap to go out of order is essentially two operations, insert elements and delete elements.

When an element is inserted into the binary heap, it is appended to the very end of the array and then floats up as the case may be. Similarly, when you delete an element, you can only delete the root node, which is the first element, and move the last element to the first index, then sink as appropriate.

/ * * *@descriptionInsert a value into the binary heap and call the siftUp method to move up */
insert(value: T): boolean {
  // Verify the inserted value
  if(value ! =null) {
    // The principle is to insert the inserted value to the very end, and then gradually siftUp until the appropriate position
    const index = this.heap.length;
    this.heap.push(value);
    // Call recursive siftUp
    this.siftUp(index);
    return true;
  }
  // If the value to be inserted is empty, return false
  return false;
}

  / * * *@descriptionExtract the heap top value and call the siftDown method to balance */
extract() {
  if (this.isEmpty()) {
    return undefined;
  }
  if (this.size() === 1) {
    return this.heap.shift();
  }
  const removedValue = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.siftDown(0);
  return removedValue;
}
Copy the code

So you can implement a binary heap.

Heap sort

So, after we talk about binary heap data structure, let’s look at the application of heap in sorting.

Since the root of the minimum heap is always the minimum of its tree, sorting a given array can be done in two steps:

  1. userewritetheSinking methodGiven an arrayThe heap,Is constructed into a binary heap;
  2. Divide the root element of the binary heap (The minimum value) and the last elementexchangeAnd then startsinking. Add the root element (The second value) and the penultimate elementexchangeAgain,sinking. And repeat untilCompletely sorted.

Note: In the first step of heap, since the leaf nodes take up at least half of the array, you only need to sink the first half of the array (i.e. the non-leaf nodes).

import { Compare, defaultCompare, ICompareFunction, swap } from ".. /.. /util";

/ * * *@description: Modified siftDown method, add a heapSize parameter, easy to sort in place *@param {array} Array Array to sort *@param {number} Index Index of the element to sink *@param {number} HeapSize Size of the current heap (after sorting) *@param {ICompareFunction} CompareFn method for comparing sizes */
function siftDown(
  array: any[],
  index: number,
  heapSize: number,
  compareFn: ICompareFunction<any>
) {
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  // First move down left
  // The key difference from the siftDown method of the class is the heapSize
  if (
    left < heapSize &&
    compareFn(array[left], array[index]) === Compare.BIGGER_THAN
  ) {
    largest = left;
  }

  // Next move down to the right
  if (
    right < heapSize &&
    compareFn(array[right], array[largest]) === Compare.BIGGER_THAN
  ) {
    largest = right;
  }

  if(largest ! == index) {/ / exchange
    swap(array, index, largest);
    // Continue the recursionsiftDown(array, largest, heapSize, compareFn); }}/ * * *@description: heap sort */
export default function heapSort(array: any[], compareFn = defaultCompare) {
  let heapSize = array.length;

  // 1. Normalize all trees except leaves into binary heaps
  for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
    siftDown(array, i, array.length, compareFn);
  }

  // 2. Swap the top element and the last element, which is equivalent to putting the top element at the back and the last element at the front
  // siftDown is then executed to re-normalize the binary heap
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    siftDown(array, 0, heapSize, compareFn);
  }
  return array;
}

Copy the code

Heap sort is known to be the only way to make optimal use of both space and time — sort in place and in the worst case it guarantees O(NlgN) time complexity. Suitable for space-constrained embedded systems or low-cost mobile devices. But it does not take advantage of caching and is not stable sorting, so it is rarely used in modern systems.

The next article will analyze the diagram.

Front-end notepad, not regularly updated, welcome to pay attention to!

  • Wechat official account: Lin Jingyi’s notepad
  • Blog: Lin Jingyi’s notebook
  • Nuggets column: Lin Jingyi’s notebook
  • Zhihu column: Lin Jingyi’s notebook
  • Github: MageeLin