Heap sort prequel

Trees and binary trees

Simple definition of a tree

A tree is a data structure, such as a directory structure. A tree is a data structure that can be defined recursively. A tree is a collection of n nodes:

  • If n=0, it’s an empty tree;
  • If n>0, it means that there exists a node as the root of the tree, and the other nodes can be divided into M sets, each of which is itself a tree. As shown below:

Some concepts of trees

  • Root node: the first node in the tree, which is node A in the figure above;
  • Leaf node: node in a tree that can no longer branch, as shown in figure B, C, H, I,.. And so on;
  • Tree depth: The deepest layer is the height of the tree. The depth of the tree in the image above is 4.
  • Degree of tree: which node in the whole tree has the most branches is the degree of tree. In the figure above, the degree of tree is 6, and node A has the most branches.
  • Parent node/Child node: The upper-layer node is the parent node of the lower-layer node, and the lower-layer node is the child node of the upper-layer node.

Binary tree

Binary tree definition

  • Trees with degrees of 2 or less
  • Each node has a maximum of two child nodes
  • The two child nodes are distinguished as left child nodes and right child nodes

As shown below:

Full and complete binary trees

Full binary tree

A binary tree is a full binary tree if it has a maximum number of nodes at each level.

Complete binary tree

Leaf nodes can only appear at the lowest and sublowest levels, and the nodes at the lowest level are concentrated in the binary tree at several positions to the left of that level.

Where :(a) is full binary tree, (b) is complete binary tree, and (c) and (d) are incomplete binary trees.

Binary tree storage mode (expression mode)

  • Chain storage
  • Sequential storage (emphasis)

Sequential storage

Simple tree is to use a list to store, as shown below:

The relationship between the number subscripts of the parent node and the left child node:

  • 0->1, 1->3, 2->5, 3->7, 4->9
  • i->2i+1

The relationship between the number subscripts of the parent node and the right child node:

  • 0->2, 1->4, 2->6, 3->8, 4->10
  • i->2i+2

Heap sort

What is a pile of

A special complete binary tree structure

  • Large root heap (large top heap) : A complete binary tree such that any node is larger than its children
  • Small root heap (small top heap) : A complete binary tree such that any node is smaller than its children

The big root heap and the small root heap are shown below:

The downward adjustment nature of the heap

Assuming that both the left and right subtrees of the following node are heaps, but the root node does not satisfy the nature of a heap, you can make it a heap by adjusting it down once.

Heap sort – Construct heap

Construction heap process: rural encircle city

  1. Starting from the last level of the tree with a child node (that is, the last non-leaf node), adjust the small subtree, then the large subtree, and finally the entire tree.

The process is as follows: 1) Start from the last level of the tree with a child node

2) Adjust the subtree (swap 3 and 5, can be regarded as changing the village head)

3) Continue to adjust the other subtree, you can see that the subtree fits the large root heap, no further adjustment is required

4) After looking at the village level, continue to look at the county level and make adjustments

5) Finally make further adjustments

As you can see, a large root heap has been built through the above process.

Then, by counting the numbers one by one (counting down), we get the sorted numbers, which is called heap sorting.

Heap sort – one by one

Each several

Let’s count the following tree (a big root heap tree constructed above) one by one. The tree is as follows:

The process of counting in turn is as follows:

1) Take the number 9 and put the last node 3 on the root node

2) Then adjust downward

3) Count 8 and place the last node 3 on the root node

4) Then make a downward adjustment

5) And so on until the tree is empty.

And the last thing that comes out is the ordered number, the sorted number, so that’s heap sort.

In general, the heap sort process is as follows:

  1. Establish a heap
  2. The top of the heap element is the largest element
  3. Remove the top element and place the last element of the heap at the top of the heap, at which point the heap can be reordered with a single adjustment
  4. The heap top element is the second largest element
  5. Repeat step 3 until the heap is empty.

Heap sort implementation


#! /usr/bin/env python
# -*- encoding: utf-8 -*-
''' @Author : Scoefield @File : heap_sort.py @Time : 2021/05/23 20:26:35 '''

from collections import deque
import random

def swap_param(L, i, j) :
    Swap the values of the parent node so that the parent node is greater than the two child nodes
    L[i], L[j] = L[j], L[i]
    return L

# Build a big root heap
def heap_adjust(L, start, end) :
    Assign the value of the parent node to temp
    temp = L[start]
    Assign the index of the parent node to I
    i = start
    The index of the left child node
    j = 2 * i
    # when j is within the length of L
    while j <= end:
        # If the child is in range and the left child is smaller than the right child
        if (j < end) and (L[j] < L[j + 1) :# switch j to the right child
            j += 1
        # If the value of the parent node is smaller than that of the child node
        if temp < L[j]:
            Assign the value of the child node to the parent node
            L[i] = L[j]
            # treat child nodes as parents
            i = j
            # Treat children of children as children
            j = 2 * i
        else:
            break
    L[i] = temp

# heap sort
def heap_sort(L) :
    We need to subtract 1 from the number of elements in the array
    L_length = len(L) - 1
    The nodes of a complete binary tree are numbered from 0 in hierarchical and left-to-right order, so the parent of the NTH node is n//2
    first_sort_count = L_length // 2
    for i in range(first_sort_count):
        # Build a big root heap
        heap_adjust(L, first_sort_count - i, L_length)
    for i in range(L_length - 1) :Swap the top element with the bottom-rightmost element of the heap
        L = swap_param(L, 1, L_length - i)
        # Build a big root heap
        heap_adjust(L, 1, L_length - i - 1)
    return [L[i] for i in range(1.len(L))]

def main() :
    Create a linked list from the list
    # L = deque([17 , 13, 40 , 22, 31, 14, 33, 56, 24, 19, 10, 41, 51, 42, 26])
    Since the heaps start at 1, introduce an auxiliary position so that the index of the array starts at 1
    # L.appendleft(0)

    # Randomly generate a list
    li = [i for i in range(20)]
    random.shuffle(li)

    # heap sort and print the sort result
    res = heap_sort(li)
    print(res)

if __name__ == '__main__':
    main()
Copy the code

Heap sort time complexity: O(nlogn).