python堆排序是什么?-Python教程-PHP中文网

python堆排序是什么?

冷漠man

发布： 2025-10-23 10:47:02

原创

601人浏览过

堆排序是一种基于二叉堆的比较排序算法，先构建最大堆再逐个将堆顶最大值与末尾元素交换并调整堆，最终实现升序排列。

python堆排序是什么?

堆排序是一种基于比较的排序算法，它利用了二叉堆这种数据结构来实现。二叉堆本质上是一个完全二叉树，并且满足堆的性质：父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。

堆排序的基本原理

堆排序主要分为两个阶段：

建堆：将无序数组构造成一个最大堆（升序排序时）或最小堆（降序排序时）。最大堆的根节点是当前堆中最大的元素。
排序：反复将堆顶元素（最大值）与堆的最后一个元素交换，然后减少堆的大小，并对新的堆顶进行调整，使其重新满足堆的性质。

这个过程持续进行，直到整个数组有序。

关键操作：堆化（heapify）

堆排序的核心是heapify函数，它的作用是让某个子树满足堆的性质。通常从最后一个非叶子节点开始，自底向上进行堆化，构建初始堆。

立即学习“Python免费学习笔记（深入）”；

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

例如：对于数组 [4, 10, 3, 5, 1]，先将其看作完全二叉树，然后从下往上调整，最终形成最大堆 [10, 5, 3, 4, 1]。

Python 实现示例

以下是一个用 Python 实现的堆排序代码：

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
<pre class='brush:python;toolbar:false;'>if left < n and arr[left] > arr[largest]:
    largest = left

if right < n and arr[right] > arr[largest]:
    largest = right

if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

登录后复制

def heap_sort(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[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)

登录后复制

调用 heap_sort([64, 34, 25, 12, 22, 11, 90]) 后，数组会变为有序状态。