Catalog

One 、 Basic concepts

Two 、 Big and small piles

3、 ... and 、 Heap implementation heapify

1、 Turn the list into a heap 【 Large item pile 】

 2、 Stack  heapify

2.1  The fourth child node of the tree , And parent nodes , The third layer is to compare the big items ,【 The red ones are the numbers after comparison and exchange 】​ edit         

2.2  The third child node of the tree , And parent nodes , The second layer is used for large item heap comparison ,【 The green ones are the numbers after comparison and exchange 】 

​2.3  The second child node of the tree , And parent nodes , The first layer is used for large item heap comparison ,【 The color change is to compare the exchanged numbers 】 ​ edit

2.4 Code to implement

 3、 Sort the heap

3.1 The last node is exchanged with the root node 【5,50 exchange 】, Cut off the last node

3.3 、 Doing... On nodes heapify, after , The root node is at the last and last node , exchange 【48,5】, Cut off the last node

 3.3 、 And so on , The root node is at the last and last node , exchange 【47,5】, Cut off the last node , Other nodes are implemented in the same way , Not one by one

3.4 The code implements this sort

  Four 、 Complete code

One 、 Basic concepts

The first thing to understand is that the heap is made up of trees , A data structure called a complete binary tree .

Two 、 Big and small piles

Big pile top ： The value of each node is greater than or equal to the value of its left and right child nodes .

Small cap pile ： The value of each node is less than or equal to the value of its left and right child nodes .
You can get a sorted list
 

For the big top heap ：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

For a small top pile ：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

3、 ... and 、 Heap implementation heapify

1、 Turn the list into a heap 【 Large item pile 】

listF = [4, 48, 3, 50, 4, 47, 5, 38, 15, 46, 19, 44, 27, 26, 36]

parent_node = (i -1) /2   # i Represents the position of the index in the tree   
lef_node = 2 * i +1  
ritht_node = 2 * 1 +2

 2、 Stack  heapify

        2.1  The fourth child node of the tree , And parent nodes , The third layer is to compare the big items ,【 The red ones are the numbers after comparison and exchange 】
        2.2  The third child node of the tree , And parent nodes , The second layer is used for large item heap comparison ,【 The green ones are the numbers after comparison and exchange 】 

 2.3  The second child node of the tree , And parent nodes , The first layer is used for large item heap comparison ,【 The color change is to compare the exchanged numbers 】 

  2.4 Code to implement

• 1、 To the fourth floor 、 The third level 、 The second floor 、 first floor , Make a recursive call heapify Method to sort the large item heap
• 2、 Implement large item heap comparison sorting

# 1、 Build a big top pile 
def buildMaxHeap(arr,n):
    # arr  Represents the currently sorted list ,n  Represents the data range of the current tree 【 And arr The number of 】
    last_node_index = n -1  # The index of the last node 
    parent_node_index = int((last_node_index-1)/2)
    if parent_node_index >= 0:
        for i in range(parent_node_index,-1,-1):
            #i  Is the number of nodes in the heap 
                heapify(arr=arr,i=i,n=n)

#2、 The child node exchanges the maximum value with the parent node 
def heapify(arr,i,n):
    #arr  Represents the currently sorted list , i  When the table of the current book parent node ,n  Represents the data range of the current tree 【 And arr The number of 】
    left = 2 * i + 1 # Find the index of the left node 
    right = 2 * i + 2 # The index of the right node in the book 
    largest = i  # Current parent

    # If there is a left node , And the value of the left node is larger , Update the index of the maximum value  left < n Transboundary 
    if left < n and arr[left] > arr[largest]:   #  Determine whether ,（left < n） Transboundary 
        largest =left
    #  If there is a right node , And the value of the right node is greater , Update the index of the maximum value 
    if right < n and arr[right] > arr[largest]: # Determine whether ,（left < n） Transboundary 
        largest = right

    # If the maximum value is not the value of the current non leaf node , Then swap the values of the current node and the child node of the maximum value 
    if largest != i:
        arr[i] ,arr[largest] =arr[largest],arr[i]  # Node values are interchanged 
        heapify(arr,largest,n)

 3、 Sort the heap

3.1 The last node is exchanged with the root node 【5,50 exchange 】, Cut off the last node

3.3 、 Doing... On nodes heapify, after , The root node is at the last and last node , exchange 【48,5】, Cut off the last node

 3.3 、 And so on , The root node is at the last and last node , exchange 【47,5】, Cut off the last node , Other nodes are implemented in the same way , Not one by one

3.4 The code implements this sort

def heapSort(arr):
    if arr == None or len(arr) ==0:
        return
    n = len(arr)
    # Build the big top heap , Become an array with a large top heap 
    buildMaxHeap(arr,n)
    if n >0:
        for a in range(n-1,0,-1):
            arr[a], arr[0] = arr[0], arr[a]
            heapify(arr,0,a)
    return arr

  Four 、 Complete code

listF = [4, 48, 3, 50, 4, 47, 5, 38, 15, 46, 19, 44, 27, 26, 36]
# 1、 Build a big top pile 
def buildMaxHeap(arr,n):
    # arr  Represents the currently sorted list ,n  Represents the data range of the current tree 【 And arr The number of 】
    last_node_index = n -1  # The index of the last node 
    parent_node_index = int((last_node_index-1)/2)
    if parent_node_index >= 0:
        for i in range(parent_node_index,-1,-1):
            #i  Is the number of nodes in the heap 
                heapify(arr=arr,i=i,n=n)

def heapify(arr,i,n):
    #arr  Represents the currently sorted list , i  When the table of the current book parent node ,n  Represents the data range of the current tree 【 And arr The number of 】
    left = 2 * i + 1 # Find the index of the left node 
    right = 2 * i + 2 # The index of the right node in the book 
    largest = i  # Current parent

    # If there is a left node , And the value of the left node is larger , Update the index of the maximum value  left < n Transboundary 
    if left < n and arr[left] > arr[largest]:   #  Determine whether ,（left < n） Transboundary 
        largest =left
    #  If there is a right node , And the value of the right node is greater , Update the index of the maximum value 
    if right < n and arr[right] > arr[largest]: # Determine whether ,（left < n） Transboundary 
        largest = right

    # If the maximum value is not the value of the current non leaf node , Then swap the values of the current node and the child node of the maximum value 
    if largest != i:
        arr[i] ,arr[largest] =arr[largest],arr[i]  # Node values are interchanged 
        heapify(arr,largest,n)

def heapSort(arr):
    if arr == None or len(arr) ==0:
        return
    n = len(arr)
    # Build the big top heap , Become an array with a large top heap 
    buildMaxHeap(arr,n)
    if n >0:
        for a in range(n-1,0,-1): # from  n -1  The last node starts 
            arr[a], arr[0] = arr[0], arr[a]
            heapify(arr,0,a)
    return arr

print(heapSort(listF))