Python 堆排序算法
最后修改于 2025年3月8日
在本文中，我们将介绍 Python 中的堆排序算法。我们将涵盖按升序和降序对数字和文本数据进行排序。最后，我们将堆排序与快速排序进行比较并进行基准测试。
算法 是用于解决问题或执行计算的循序渐进的过程。算法是计算机程序的骨干。
排序 是按特定顺序（例如升序或降序）排列数据的过程。排序是计算机科学中的一项基本操作。
常用排序算法
一些常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
堆排序算法
堆排序是一种基于比较的排序算法。它使用二叉堆数据结构来对元素进行排序。该算法的时间复杂度为 O(n log n)，对于大型数据集来说非常高效。
堆排序示例
以下示例演示了 Python 中用于数字数据的堆排序。
heap_sort.py
#!/usr/bin/python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)
该示例使用堆排序按升序对整数数组进行排序。
$ ./heap_sort.py Sorted array: [5, 6, 7, 11, 12, 13]
文本数据的堆排序
堆排序也可用于对文本数据进行排序。以下示例按升序对字符串列表进行排序。
heap_sort_text.py
#!/usr/bin/python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = ["banana", "apple", "cherry", "date"]
heap_sort(arr)
print("Sorted array:", arr)
该示例按升序对字符串列表进行排序。
$ ./heap_sort_text.py Sorted array: ['apple', 'banana', 'cherry', 'date']
降序堆排序
要按降序对数据进行排序，请修改 heapify 函数以构建最小堆而不是最大堆。
heap_sort_desc.py
#!/usr/bin/python
def heapify(arr, n, i):
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] > arr[left]:
smallest = left
if right < n and arr[smallest] > arr[right]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
heapify(arr, n, smallest)
def heap_sort_desc(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)
arr = [12, 11, 13, 5, 6, 7]
heap_sort_desc(arr)
print("Sorted array in descending order:", arr)
该示例按降序对整数数组进行排序。
$ ./heap_sort_desc.py Sorted array in descending order: [13, 12, 11, 7, 6, 5]
堆排序与快速排序
堆排序和快速排序都是高效的排序算法。堆排序保证时间复杂度为 O(n log n)，而快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下可能退化到 O(n^2)。
堆排序和快速排序的基准测试
以下示例使用 Python 的 timeit 模块对堆排序和快速排序进行基准测试。
benchmark.py
#!/usr/bin/python
import timeit
import random
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [random.randint(0, 1000) for _ in range(1000)]
heap_time = timeit.timeit(lambda: heap_sort(arr.copy()), number=100)
quick_time = timeit.timeit(lambda: quick_sort(arr.copy()), number=100)
print(f"Heap Sort Time: {heap_time}")
print(f"Quick Sort Time: {quick_time}")
该示例在包含 1000 个随机整数的列表上对堆排序和快速排序进行基准测试。
来源
在本文中，我们通过示例解释了 Python 中的堆排序算法。
作者
列出所有 Python 教程。