preface

In Dart’s implementation of several basic sorting algorithms, the heapsort implementation is only briefly analyzed with annotations. This article is an extension of that. We’ll talk more about binary heaps and heap sorting.

Binary heap

A binary heap is a complete or nearly complete binary tree.

A binary heap satisfies two characteristics of a heap:

  • Structure: The heap is always a complete tree. That is, all nodes except the lowest layer are filled with elements, and the lowest layer is filled as far left as possible to right

  • Heap orderliness: The value of the parent node always maintains a fixed order relationship (greater or less than) with the key value of any child node

Maximum heap when the value of the parent node is always greater than or equal to the key value of any child node.

Minimum heap when the value of the parent node is always less than or equal to the key value of any child node.

Structural properties

Because a complete binary tree is regular, it is always represented by an array.

  1. If the root node is at position 1 in the array, the NTH child node is at 2n and 2n+1 respectively.

  2. If the subscript of the storage array is based on 0, then the children of the node with subscript I are 2i+1 and 2i+2, and the parent of the child node I is in position (i-1)/2

The array in the figure below corresponds to the complete binary tree in the figure above

Heap sequence sex

The heap order property is what makes binary heaps fast because the parent node is always larger (smaller) than the child node, so finding the largest (smallest) element becomes easy.

In the figure below, the tree on the left is a heap, while the tree on the right is not.

Basic heap operations

Insert (filter up strategy)

When inserting an element into X into the heap, to ensure that the tree is a complete tree, we need to create a hole in the next available position, and then place element X in that hole. If X does not break the heap orderliness at the current location, the insertion is complete. However, this is often not the case. At this point we need to swap the parent node of the hole with the newly created node. This is done continuously with the parent node until X reaches its proper position, which is the heap ordering position. Demonstrate the process with pictures as follows:

The original tree Create a hole in the next available location, and place element 67 in that hole
The heap ordering is not satisfied Swap places with the parent node
The heap ordering is not satisfied Swap places with the parent node
The animation looks like this:

This strategy is called upfiltering, where new elements move up the heap to find their proper place.

Insert is easy to implement with the following code:

///The insert
void insert(int num) {
  ///Sort the data backwards in order
  heapList.add(num);

  ///Start on the filter
  percolateUp(num);
}

///On the filter
void percolateUp(int num) {
  ///Find the last new element first
  ///And constantly compared to its parent. If it is larger than its parent, it is moved up
  ///Swap upward until the destination is no longer larger than the parent node
  for (var hole = heapList.length - 1;
      heapList[hole].compareTo(heapList[((hole - 1) ~ /2)]) > 0;
      hole = (hole - 1) ~ /2) {
    heapList[hole] = heapList[(hole - 1) ~ /2];
    heapList[(hole - 1) ~ /2] = num; }}Copy the code
Delete the root node (maximum or minimum element) (filter down strategy)

It’s easy to find the largest or smallest element, which is the root node. The hard part is deleting it. When the root node is deleted, a hole is created at the root. One element is missing from the heap, so the last element must be moved to the appropriate position. We can first put the last element directly into the cavity, and then compare it with its two sons, constantly pushing the target acupoint down. Similar to insertion, the animation looks like this:

Delete binary heap with the following code:

///Delete operation
void deleteRoot() {
  ///Put the element of the last node into the first node and delete the last node
  heapList[0] = heapList[heapList.length - 1];
  heapList.removeAt(heapList.length - 1);

  ///Start the filter
  percolateDown();
  systemOutList('Delete root node');
}

///The filter
void percolateDown({int targetIndex = 0{})///Find the root node first, which already contains the last element before deleting it
  ///And constantly compare it with the smallest byte point and swap it with the smallest element larger than it
  ///Keep swapping down until the destination is no longer smaller than any child node
  var heapLength = heapList.length - 1;
  int targetChild;
  for (var hole = targetIndex; 2 * hole + 1 <= heapLength; hole = targetChild) {
    ///Find the left child node and default it as the target acupoint
    targetChild = 2 * hole + 1;
    ///Find the smallest child node as the target acupoint
    ///If the left child is smaller than the right child, the target node is the right child
    if (targetChild < heapList.length - 1 &&
        heapList[targetChild].compareTo(heapList[targetChild + 1]) < 0) {
      targetChild++;
    }
    if (heapList[targetChild].compareTo(heapList[hole]) > 0) {
      ///If the value in the target acupoint is less than its smallest child node
      ///So filter it down, swap the two;
      var temp = heapList[hole];
      heapList[hole] = heapList[targetChild];
      heapList[targetChild] = temp;
    } else {
      break; }}}Copy the code
An array of chemical

When you want to convert an array to a binary heap array, you can do this using n insertions. But there’s a better way to do it.

The normal operation is to put the data into the tree in any order and keep it structural. Now we find the last non-leaf node. According to the structure described above: the parent node of the last leaf node is the last non-leaf node, and the parent node of child node I is at position (i-1)/2, then the first non-leaf node is (Leng-1)/2. When the last non-leaf node is found, it is filtered down. Then all non-leaf nodes are traversed to realize the up-filtering of large data.

The summary steps are as follows:

  1. Put data into the tree at will, but keep the heap structured;

  2. Find the first non-leaf node and try to filter it down;

  3. Continue to look up the last non-leaf node and try to filter it down;

  4. Repeat step 3 until you reach the root node.

The animation process is as follows:

The code is also simple:

///Heap the array
void buildHeap(List<int> list){
  heapList = List.from(list);
  ///BeginIndex is the first non-leaf node
  var beginIndex = heapList.length~/2 - 1;
  ///Compare the first non-leaf node with its children
  ///Find the data in the left and right child nodes that is larger than the current node and swap it with the parent node
  ///Keep pushing the maximum to the bottom of the heap.
  ///Notice that the value of the current position is filtered down
  ///In contrast, for larger values, it is an up-filtering process
  for (var i = beginIndex; i >= 0; i--) { percolateDown(targetIndex: i); }}Copy the code

Heap sort

At this point, heap sort is in the air — we just heap the array and keep fetching the root node:

///Raw heap sort
List<int> heapSore(){
  var sortList= <int> [];///Heaped-up data
  var rank = heapList.length;
  for(var i = 0; i < rank; i++){///Take out heel node
    sortList.add(heapList[0]);
    deleteRoot();
  }
  print('Sorted array:$sortList');
  return sortList;
}
Copy the code

Animation shows a sorting process:

The optimized sort code can be referred to: heap sort

Summary and reference

For more sorting algorithms, see: Basic sorting algorithms

Binary Heap

Related source code please refer to: Demo