Python实现堆排序案例详解

堆排序简介

堆排序是一种基于树形数据结构的排序算法，它的时间复杂度为 O(nlogn)，堆排序分为大根堆和小根堆，当堆为大根堆时，堆中每个节点的值都大于或等于其孩子节点的值，当堆为小根堆时，堆中每个节点的值都小于或等于其孩子节点的值。

堆的基本概念

堆是一种完全二叉树，它可以用数组来表示，数组下标从 1 开始，对于下标为 i 的节点，它的左孩子下标为 2i，右孩子下标为 2i+1，父节点下标为 i/2。

堆排序的思路

堆排序的基本思路是，先建立堆，然后依次取出堆顶元素放在末尾，之后重新调整堆结构，直到排完序为止。

堆排序的代码实现

下面是 Python 实现堆排序的代码示例：

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

    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, -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)

堆排序示例说明

示例1

对于数组 [12, 11, 13, 5, 6, 7] 进行堆排序。

首先建立的大根堆为：

          13
       /       \
    12         7
   /  \       /  \
 11    5     6    -1
 / \   / \
-1 -1 -1 -1

将堆顶元素 13 取出放在末尾，之后重新调整堆结构，得到新的大根堆：

          12
       /       \
    11         7
   /  \       /  \
 -1   5     6    -1
 / \   / \
-1 -1 -1 -1

依次类推，得到排好序的数组 [5, 6, 7, 11, 12, 13]。

示例2

对于已经有序的数组 [5, 6, 7, 11, 12, 13] 进行堆排序。

首先建立的大根堆为：

          13
       /       \
    12         7
   /  \       /  \
 11    6     5    -1
 / \   / \
-1 -1 -1 -1

可以看到，堆结构没有发生任何变化，因此直接输出已排好序的数组 [5, 6, 7, 11, 12, 13]。

结语

以上就是 Python 实现堆排序的详细攻略，希望能够对大家学习和理解堆排序算法有所帮助。