Algorithm principle

First, a heap sort animation demo picture:

Image from Wikipedia

1. I have to talk about binomial trees

To understand a heap, you need to first understand a binary tree, which in computer science is a tree structure with at most two subtrees per node. Subtrees are usually called “left subtrees” and “right subtrees”. Binary trees are often used to implement binary search trees and binary heaps.

Each node of a binary tree has at most two subtrees (there is no node whose degree is greater than 2). The subtrees of a binary tree can be divided into left and right, and the order cannot be reversed. The i-layer of binary tree has at most 2I-1 nodes. The binary tree of depth K has at most 2K-1 nodes. For any binary tree T, if its terminal node number is N0 and the node number of degree 2 is n2, then N0 = n2 + 1.

There are three main differences between trees and binary trees:

  • A tree has at least one node, whereas a binary tree can have zero nodes
  • The maximum degree of a node in a tree is unlimited, whereas the maximum degree of a node in a binary tree is 2
  • A tree has no left and right nodes, whereas a binary tree has left and right nodes

Binary tree is divided into complete binary tree and full binary tree.

Full binary tree: A full binary tree with depth K and 2K-1 nodes is called full binary tree

Binary tree full binary tree full binary tree

Complete binary tree: a binary tree with depth K and n nodes is called a complete binary tree if and only if each node corresponds to nodes numbered 1 through n in a full binary tree with depth K

Complete binary tree with depth 3

2. What is a heap?

Heap heap (binary) can be regarded as a complete binary tree, a complete binary tree is the nature of the “good”, in addition to the bottom, each layer is full, the heap array can be used to say (ordinary general binary tree is usually expressed in list as the basic container), and each node corresponds to an element of the array.

The diagram below shows the relationship between a heap and an array

The interrelation between heap and array

For the subscript I of a given node, it is easy to calculate the subscripts of the parent node and the child node:

  • Parent(I) = floor(I /2), subscript of the Parent of I
  • Left(I) = 2i, the subscript of the Left child of I
  • Right(I) = 2i + 1, the subscript of the Right child of I

Binary heaps are generally divided into two types: maximum heap and minimum heap.

The maximum heap:

  • The largest element value in the largest heap occurs at the root (the top of the heap)
  • Each parent node in the heap has an element value greater than or equal to its child (if present)

The maximum heap

The minimum heap:

  • The minimum element value in the minimum heap occurs at the root (the top of the heap)
  • Each parent node in the heap has an element value less than or equal to its child (if present)

The minimum heap

3. Principle of heap sort

Heap sort is to take the maximum number at the top of the maximum heap, adjust the remaining heap to the maximum heap, and take the maximum number at the top again. This process continues until there is only one remaining heap. Define the following operations in the heap:

  • Max-heapify: Adjusts the end child of the heap so that the child is always smaller than the parent
  • Create a build-max-heap: Reorder all the data in the Heap to make it the maximum Heap
  • Heap-sort: a recursive operation that removes bits at the root of the first data and adjusts the maximum Heap

Before we move on, one thing to note is that arrays are zero-based, which means that our heap data structure model is going to change

Zero-Based

Accordingly, several calculation formulas should be adjusted accordingly:

  • Parent(I) = floor((i-1)/2), subscript of the Parent node of I
  • Left(I) = 2i + 1, the Left subscript of I
  • Right(I) = 2(I + 1), the subscript of the Right child of I

MAX‐HEAPIFY is the core subroutine for creating the maximum heap, which preserves the properties of the maximum heap. The process of action is shown in the figure below:

Max-Heapify

Since the heap still violates the heap nature after one adjustment, we need to recursively test the heap to make the whole heap meet the heap nature, which can be expressed in JavaScript as follows:

** @heapsize heapSize ** */ function maxHeapify(array, index, maxHeapify) heapSize) { var iMax = index, iLeft = 2 * index + 1, iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax ! = index) { swap(array, iMax, index); maxHeapify(array, iMax, heapSize); } function swap(array, I, j) {var temp = array[I]; array[i] = array[j]; array[j] = temp; }Copy the code

In general, recursion is mostly used in divide-and-conquer, and there is no need for divide-and-conquer. Furthermore, recursive calls require stack pushing/clearing, which has a slight performance disadvantage compared to iteration. Of course, by the 20/80 rule, this is negligible. But if you feel that recursion is a pain in the ass, you can also use iteration, such as the following:

** @heapsize heapSize ** */ function maxHeapify(array, index, maxHeapify) heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax ! = index) { swap(array, iMax, index); index = iMax; } else { break; } } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; }Copy the code

Build-max-heap (build-max-heap) transforms an array into a maximum Heap, taking two parameters: array and Heap size. Build-max-heap calls Max-heapify from bottom up to transform the array and Build the maximum Heap. Because max-Heapify can guarantee that all nodes after subscript I meet the maximum heap property, bottom-up calls to Max-Heapify can maintain this property during transformation. If the maximum number of Heap elements is N, then build-max-heap calls max-heapify from Parent(n) up. The process is as follows:

Build-Max-Heap

It is described in JavaScript as follows:

function buildMaxHeap(array, heapSize) { var i, iParent = Math.floor((heapSize - 1) / 2); for (i = iParent; i >= 0; i--) { maxHeapify(array, i, heapSize); }}Copy the code

Heap-sort is an interface algorithm for Heap sorting. Heap-sort first calls build-max-heap to transform an array into a maximum Heap, then swaps the top and bottom elements of the Heap, then raises the bottom, and finally calls Max-Heapify again to preserve the maximum Heap nature. Since the top element is necessarily the largest element in the heap, after one operation, the largest element in the heap is separated out of the heap, and after n-1 repetitions, the array is arranged. The whole process is as follows:

Heap-Sort

It is described in JavaScript as follows:

function heapSort(array, heapSize) { buildMaxHeap(array, heapSize); for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); }}Copy the code

JavaScript language implementation

Finally, the complete javascript code looks like this:

function heapSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax ! = index) { swap(array, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(array) { var i, iParent = Math.floor(array.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(array, i, array.length); } } function sort(array) { buildMaxHeap(array); for (var i = array.length - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } return array; } return sort(array); }Copy the code

Refer to the article

  • Wikipedia
  • Wikipedia, heap sort
  • Wikipedia, binary tree
  • Algorithms Chapter 6 Heapsort
  • Heap Sort
  • Heap to heap sort
  • Heap sort
  • Heap Sort algorithm learning
  • Sorting Algorithm Animations