directory

  1. Basic data structure

  2. Heap sort

  3. data

  4. harvest

In order to understand what heap sort is, we need to understand binary trees and heaps first.

1. Basic data structure

Array, sequential storage of linked lists in memory: unidirectional linked lists, bidirectional linked lists, bidirectional cyclic linked lists. Storage in memory is random.

Both arrays and linked lists are linear data structures, where arrays are efficient at lookup and linked lists are efficient at insertion and deletion. Arrays and linked lists are both stored in the physical structure of data storage, in memory. Queues, stacks, trees and graphs are logical structures abstracted for better understanding and programming. Logical structure is abstract and depends on physical structure

Image from Comic Book Algorithm

2. A nonlinear logical structure. In a data structure, a tree is positioned as:

A tree is a finite set of n nodes. When n=0, it becomes an empty tree. In any non-empty tree, it is special as follows

  1. Tangent has only one specific root node
  2. When n>1, the remaining nodes can be divided into m disjoint finite sets, and each set itself is a tree, which becomes a subtree of the root.

Binary tree A binary tree is a special tree with a maximum of two child nodes per node. Binary trees can be stored in arrays or linked lists.

The image is an edit of a screenshot from Comic Algorithm

It can be divided into full binary tree, complete binary tree and so on

The image is an edit of a screenshot from Comic Algorithm

From the perspective of different ways to solve the self-equilibrium problem of “super many on one side and little on the other side”, there is the concept of red-black tree

Binary heap Binary heap is a complete binary tree in nature, its storage mode is not a chain structure, but sequential storage in the form of an array.

There are two types: maximum heap and minimum heap Maximum heap (big top heap) : the value of any parent node is greater than or equal to the value of its children, i.e. the top of the heap is the largest element in the heap. Minimum heap (small top heap) : The value of any parent node is less than or equal to the value of its children, i.e. the top of the heap is the smallest element in the heap.

When a new node is inserted or removed, the binary heap automatically adjusts the node position based on the type.

Binary heap is the basis of heap sorting and prioritization

Second, heap sort

From the previous section, we have a basic understanding of data structures, the structure of the heap and how it is stored. We can take advantage of binary heap sorting and automatic adjustment of node positions to achieve sorting.

If you want to use a binary heap for sorting, there are two steps

  1. Organize the unordered number into a binary heap (let’s build a big top heap here to lay a foundation for sorting the next step from small to large)
  2. The top element and the end of the binary heap are cyclically swapped, the last child node is cut off (i.e. the number of heaps is reduced by one), and the heap is adjusted again to produce a new big top heap.

If you encounter an unordered complete binary tree and want to become a heap, start at depth-1 and work your way up

Here we use arrays to represent a complete binary tree, so that we can take its parent and its left and right children from any node

If the subscript of the child node is I, pass parent = (i-1)/2; Calculates the location of the parent node

So we can calculate the position of the last non-leaf node. For example, if the maximum subscript of array is array.size-1, then the position of the last non-leaf node is

Parent = (array.size-1-1)/2 = (array.size-2)/2Copy the code

If the location of the parent node is known, calculate the position of the left and right nodes as follows

leftPos = 2*parentPos+1;
rightPos = 2*parentPos+2;
Copy the code

2.1 Building the big Top Heap

The big top heap satisfies the following two conditions

    1. Conforms to a complete binary tree
    1. All the parent nodes have values greater than the child nodes

Let’s start by building a big top heap. To better understand this, let’s draw a step-by-step dismantling process

Here is the code implementation for building the largest heap.

void heapify(int* a,int length,int parentPos) { if(parentPos >= length) { return; } // The subscript of the left child is int cl = 2*parentPos +1; Int cr = 2*parentPos+2; Int Max = parentPos; int Max = parentPos; If (cr <length && a[cr]>a[Max]) {Max = cr; if(cr <length && a[cr]>a[Max]) {Max = cr; If (cl <length && a[cl]>a[Max]) {Max = cl; } if(Max! // Swap (a, Max,parentPos) {// Swap (a, Max,parentPos); ParentPos = parentPos = parentPos Heapify (a,length, Max); heapify(a,length, Max); }} /** * @brief Build large top heap * satisfy the following two conditions * 1. The value of all the parent nodes is greater than the value of the child nodes * * @param a * @param length */ void buildHeap(int *a,int length) lastNode = length -1; Int parent = (lastNode-1)/2; int parent = (lastNode-1)/2; For (int I = parent; for(int I = parent; i>=0; i--) { heapify(a,length,i); }}Copy the code

2.2 the heap sort

With the big top heap, we can do the second step of heap sort, implement the steps of sorting the array from small to large:

    1. The root node is swapped with the last node, and the last node is the maximum value.
    1. Subtract the legth of the node by 1, that is, remove the last confirmed maximum value
    1. Heapify is heaped from the root node so that the maximum value runs to the following node

Let’s go through the disassembly process step by step by drawing a picture

The final complete code implementation is as follows

#include <iostream> #include<array> #include<algorithm> using namespace std; void printSortArray(int myarray[],int size){ for(int k=0; k<size; k++) { cout<<myarray[k]<<" "; } cout<<endl; } void swap(int *a,int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j]=tmp; } /** * @brief heaps from top to bottom ** @param a: heap data * @param length: heap length * @param parentPos: Void heapify(int* a,int length,int parentPos) {if(parentPos >= length) {return; void heapify(int* a,int length,int parentPos) {return; } // The subscript of the left child is int cl = 2*parentPos +1; Int cr = 2*parentPos+2; Int Max = parentPos; int Max = parentPos; If (cr <length && a[cr]>a[Max]) {Max = cr; if(cr <length && a[cr]>a[Max]) {Max = cr; If (cl <length && a[cl]>a[Max]) {Max = cl; } if(Max! // Swap (a, Max,parentPos) {// Swap (a, Max,parentPos); ParentPos = parentPos = parentPos Heapify (a,length, Max); heapify(a,length, Max); }} /** * @brief Build large top heap * satisfy the following two conditions * 1. The value of all the parent nodes is greater than the value of the child nodes * * @param a * @param length */ void buildHeap(int *a,int length) lastNode = length -1; Int parent = (lastNode-1)/2; int parent = (lastNode-1)/2; For (int I = parent; for(int I = parent; i>=0; i--) { heapify(a,length,i); * With a big top heap, how to sort the heap? * The steps are as follows: * 1. Swap the root node with the last node, and the value of the last node is the maximum value. * 2. Subtract 1 from the legth of the node, i.e., remove the last confirmed maximum value * 3. Then heapify from the root node, * * * @param a * @param length */ void heapSort(int *a,int length) {for(int I =length - 1; i>=0; // swap(a,0, I); // swap(a,0, I); // After the swap, adjust to the big top heap. Note that the length is already -1, i.e. remove the confirmed maximum value of the last bit. heapify(a,i,0); }} int main(void) {myarray[] ={6,7,1,2,10,5,8,3,4}; int size = sizeof(myarray)/sizeof(myarray[0]) ; cout<<"size="<<size<<endl; // First build the big top heap buildHeap(myarray,size); HeapSort (myarray,size); printSortArray(myarray,size); return 0; } -- "@"size=9\r\n" @"1 2 3 4 5 6 7 8 10 \r\n"Copy the code

So that’s heap sorting, and in the next article we’ll continue to practice selection sorting and insertion sorting, learning and growing together.

Third, information

The comic algorithm in the algorithm [heap sort (heapsort)] : www.bilibili.com/video/BV1Eb…

Four, harvest

  1. Understand the characteristics of basic data structures (arrays, linked lists, binary trees, binary heaps)
  2. Understand and practice building maximum heaps
  3. Understand heap sort process and code implementation

Thank you for reading

Next we continue to learn practical sorting algorithms: selection sorting and insertion sorting, welcome to pay attention to the public account “audio and video development journey”, learn to grow together.