How to implement heap sort algorithm using Python?

How to implement the heap sort algorithm using Python?

Heap sort is a sorting algorithm based on a binary heap, which takes advantage of the properties of a complete binary tree. Heaps can be divided into two types: max heap and min heap. The max heap requires that the value of the parent node is greater than or equal to the value of its child nodes, while the min heap requires that the value of the parent node is less than or equal to the value of its child nodes. In heap sort algorithm we use max heap.

The following are the specific steps and code examples for using Python to implement heap sorting:

Step 1: Build the maximum heap
In the process of building the maximum heap, we need to adjust the heap structure so that The value of each parent node is greater than or equal to the value of its child nodes.

First, we define a function heapify to implement the heap adjustment process. This function accepts three parameters: the heap list heap, the size of the heap, and the index of the parent node to be adjusted.

def heapify(heap, size, parent):
    largest = parent
    left = 2 * parent + 1
    right = 2 * parent + 2

    if left < size and heap[left] > heap[largest]:
        largest = left

    if right < size and heap[right] > heap[largest]:
        largest = right

    if largest != parent:
        heap[parent], heap[largest] = heap[largest], heap[parent]
        heapify(heap, size, largest)

Next, we define a function build_heap to build the maximum heap. This function accepts a list as argument and builds a max-heap based on the elements in the list.

def build_heap(heap):
    size = len(heap)

    for i in range(size // 2 - 1, -1, -1):
        heapify(heap, size, i)

Step 2: Heap sort
After building the maximum heap, we can use the properties of the maximum heap for sorting. The idea of ​​​​heap sorting is to exchange the top element of the heap (maximum value) with the last element each time, adjust the top of the heap, then take out the maximum value, and adjust again until there is only one element left in the heap.

The following are the specific steps and code examples for sorting using the heap sort algorithm:

def heap_sort(heap):
    size = len(heap)

    build_heap(heap)

    for i in range(size - 1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        heapify(heap, i, 0)

Step 3: Test the code
Now, we can use some test data to verify that our code correct.

if __name__ == "__main__":
    # 测试数据
    data = [4, 10, 3, 5, 1]

    heap_sort(data)

    print("排序结果:", data)

Run the above code, the output result is: sorting result: [1, 3, 4, 5, 10], indicating that the heap sort algorithm is correct.

Summary:
Heap sort is an efficient sorting algorithm with a time complexity of O(nlogn). Taking advantage of the complete binary tree properties of the heap, we can achieve this by building a maximum heap and performing heap sorting. Using the Python language, we can implement the heap sort algorithm by writing the heap adjustment function (heapify), the maximum heap building function (build_heap), and the heap sort function (heap_sort). Test code helps us verify that our implementation is correct.

The above is the detailed content of How to implement heap sort algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!