Concept and code of implementing heap sort algorithm in Python

The prerequisite for understanding the heap sort algorithm is to know the complete binary tree and heap data structure. The heap sort algorithm visualizes the array as a complete binary tree, so it is also called a "heap".

Heap sorting algorithm principle

1. According to the maximum heap attribute, the largest item in the data group is stored in the root node

2. Remove the root element and place it at the end of the array (nth position), put the last item of the tree into the vacant position.

3. Reduce the heap size by 1.

4. Heap the root element again

5. Repeat the process until all items in the list are sorted

Python implements heap sorting algorithm

指定数组arr= 1 12 9 5 6 10

def heapify(arr, n, i):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
def heapSort(arr):
      n = len(arr)
  
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
  
          heapify(arr, i, 0)
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end=&#x27;&#x27;)

The above is the detailed content of Concept and code of implementing heap sort algorithm in Python. For more information, please follow other related articles on the PHP Chinese website!