How to implement heap sort in python (code example)

The content of this article is about how to implement heap sorting in python (code example). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Heap sort

Heap sort refers to a sorting algorithm designed using the data structure of a heap. Stacking is a structure that approximates a complete binary tree, and at the same time satisfies the properties of stacking: that is, the key value or index of a child node is always smaller than (or larger than) its parent node (but there is no guarantee that all left subtrees are smaller than the right subtree, and vice versa. Also). Heap sort can be said to be a selection sort that uses the concept of heap to sort. Divided into two methods:

Big top heap: the value of each node is greater than or equal to the value of its child node, used in ascending order in the heap sorting algorithm;

Small top heap : The value of each node is less than or equal to the value of its child node, used in descending order in the heap sort algorithm;

The average time complexity of heap sort is Ο(nlogn).

Algorithm steps

1. Create a heap H[0...n-1]; (**Adjust the child nodes of non-leaf nodes to build a heap **)

2. Swap the head of the heap (maximum value) and the tail of the heap;

3. Reduce the size of the heap by 1 and call shift_down(0). The purpose is to convert the new Adjust the data at the top of the array to the corresponding position;

4. Repeat step 2 until the heap size is 1.

Python code implementation

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr

The above is the detailed content of How to implement heap sort in python (code example). For more information, please follow other related articles on the PHP Chinese website!