# Algorithms: heap sort

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.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 = arr, 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 = arr, arr[a]
heapify(arr,0,a)
return arr

print(heapSort(listF))``````

https://cdmana.com/2022/174/202206231839325902.html

Scroll to Top