Today we are going to take a closer look at heap sorting.

The code for this article is here.

Heapsort

Heapsort refers to a sort algorithm designed by using heap data structure. A heap is a complete binary tree structure that also satisfies the heap property: the key value or index of a child node is always smaller than (or greater than) its parent node. Heap sort can be said to be a selection sort that uses the concept of heap to sort.

To understand heap sorting, let’s first understand the concept of binary trees

Binary tree

Binary tree refers to the ordered tree in which the degree of nodes is not greater than 2. It is the simplest and most important tree.

Related terms in binary trees

  1. Node: Contains a data element and information that points to subtree branches
  2. Degree of nodes: The number of subtrees a node has is called the degree of a node
  3. Leaf node: also called terminal node, node with no subtree or node with degree 0
  4. Branch node: also called non-terminal node, node of degree not 0.
  5. Degree of tree: The maximum degree of all nodes of a tree species.
  6. The hierarchy of nodes: starting from the root node, assume that the root node is layer 1, the child node of the root node is layer 2, and so on. If a node is at layer L, its child node is at layer L+1
  7. Tree depth: also known as the height of the tree, the maximum level of all nodes in the tree is called the tree depth
  8. Ordered tree: A tree is called an ordered tree if its subtrees are ordered in sequence
  9. Unordered tree: A tree is called unordered if its subtrees are not in order
  10. A forest consists of m (m≥0) trees that do not intersect each other. If the root of a non-empty tree is deleted, the tree becomes a forest consisting of the subtrees of the original root

Basic properties

  • Each node has a maximum degree of 2
  • The node with degree 0 has one more node than the node with degree 2. Let the node with degree 0 be N0, the node with degree 1 be N1, and the node with degree 2 be N2. So the sum is n0+n1+n2, and the total number of edges is 0 times n0+ 1 times n1+ 2 times n2. And we know that the total number of sides is equal to the sum minus 1, so n0+n1+n2−1 = 0·n0+ 1·n1+ 2·n2, that is, n0−1 =n2.
  • A binary tree of depth h contains at most 2H-1 nodes

Special binary tree

Complete Binary tree

A binary tree of depth K with n nodes is numbered from top to bottom and from left to right. If the node numbered I (1≤ I ≤n) is in the same position as the node numbered I in the full binary tree, the binary tree is called a complete binary tree.

  • The numbering of the parent and child nodes has a computable relationship so there is no need to store edge information
  • We can store e in continuous space
Full binary tree

There are only binary trees with degrees 0 and 2

Perfect Binary Tree

Every layer is full, symmetrical and perfect.

Note: The definition of several binary trees may be different in different data notes, so please confirm it when mentioned in practical situations.

Heap (Heap)

Heap is a general term for a special kind of data structure in computer science. A heap is usually an array object that can be thought of as a tree. A heap always satisfies the following properties

  • The value of a node in the heap is always no greater than or less than the value of its parent
  • The heap is always a complete binary tree

Big pile top

In any triplet, the parent node is greater than two children. The root node is the maximum.

Small cap pile

In any triplet, the parent is less than two children. The root node is the minimum.

Basic operations of the heap (with the big top heap as an example)

  • Insert the tail
    • Larger than the parent, swap recursively with the parent to adjust upwards
    • This process is called SIFT UP
  • The head pops up
    • Recursively adjust down with the last element (leaf) complement
    • This process is called SIFT DOWN

The formula for heap sort

  1. Build the unnecessary sequence into a heap, and select the big top heap or the small top heap according to the ascending and descending requirements;
  2. Swap the heap element with the heap tail element
  3. Think of this as a heap top element pop-up operation
  4. Adjust the heap according to the strategy after the header pops up, repeating 2 to 4 until the heap element is 1.

The illustration

Code implementation

class Heap {
  constructor(data) {
    this.data = data
    this.compartor = (a, b) = > a - b
    this.heapify()
  }

  size() {
    return this.data.length
  }

  heapify() {
    if (this.size() < 2) {
      return
    }

    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i)
    }
  }

  peek() {
    if (!this.size()) return null
    return this.data[0]}offer(val) {
    this.data.push(val)
    this.bubbleUp(this.size() - 1)}poll() {
    if (!this.size()) return null
    if (this.size() === 1) return this.data.pop()

    let res = this.data[0]

    this.data[0] = this.data.pop()

    if (this.size()) {
      this.bubbleDown(0)}return res
  }

  swap(i, j) {
    if (i === j) {
      return
    }
    ;[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }

  bubbleUp(index) {
    // Adjust up, we need to adjust up to 0 position

    while (index) {
      // Get the parent of the current node,
      const parenIndex = (index - 1) > >1

      // const parenIndex = Math.floor((index - 1) / 2);
      // const parenIndex = (index - 1) / 2 | 0;
      // Compare the value of the parent node with our current value.
      if (this.compartor(this.data[index], this.data[parenIndex]) < 0) {
        //if swaps parent and child nodes
        this.swap(index, parenIndex)
        // index takes a step up for the next swap

        index = parenIndex
      } else {
        // Prevent dead loops.
        break}}}bubbleDown(index) {
    // We want to get the maximum index and ensure that we do not swap out of bounds.

    let lastIndex = this.size() - 1
    while (index < lastIndex) {
      // Get the subscripts of the left and right sons
      let leftIndex = index * 2 + 1
      let rightIndex = index * 2 + 2
      // Node to be switched
      let findIndex = index
      if (
        leftIndex <= lastIndex &&
        this.compartor(this.data[leftIndex], this.data[findIndex]) < 0
      ) {
        findIndex = leftIndex
      }

      if (
        rightIndex <= lastIndex &&
        this.compartor(this.data[rightIndex], this.data[findIndex]) < 0
      ) {
        findIndex = rightIndex
      }
      if(index ! == findIndex) {this.swap(index, findIndex)

        index = findIndex
      } else {
        break}}}}const heapArr = getRandomArr();
console.log('before heapArr ===>', heapArr);
const len = heapArr.length;
const minHeap = new Heap(heapArr)
const resHeapArr = []
for (let i = 0; i < len; i++) {
	resHeapArr.push(minHeap.poll())
}
console.log('after heapArr ===>', resHeapArr)
Copy the code