数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中的堆排序是什么？
堆排序是一种基于二叉堆数据结构的排序技术。为了进行堆排序，您需要熟悉二叉树和二叉堆。
什么是完全二叉树？
完全二叉树是一种树形数据结构，其中除了最后一层外，所有层都完全填充。最后一层必须从左侧填充。
什么是二叉堆？
二叉堆是二叉树的一种特殊情况。二叉堆有两种类型：
最大堆 - 每层上的父节点都大于其子节点。
最小堆 - 每层上的父节点都小于其子节点。
完全二叉树的数组表示
由于二叉堆的空间效率高，因此可以表示为数组。如果父节点存储在索引 I 处，则左子节点可以通过 2 * i + 1 计算，右子节点可以通过 2 *i + 2 计算。假设索引从 0 开始。
堆排序算法
从完全二叉树构建最大堆。
删除根节点并将其替换为堆中的最后一个元素，将堆的大小减少 1，然后再次从剩余节点构建最大堆。
重复步骤 2，直到只剩下 1 个节点。
从完全二叉树构建最大堆
这是从完全二叉树构建最大堆的代码，其中两个子节点与根节点进行比较。如果较大的元素不是根节点，则将较大的元素与根节点交换。这是一个递归过程。当前小于其子节点的根节点会持续与其较低的子树进行比较，直到到达其正确的位置。
以下代码从完全二叉树构建最大堆，该二叉树基本上是我们想要排序的数组。
def heapify(arr, n, i): # Find largest among root and children 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 root is not largest, swap with largest and continue heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
堆排序
此时，我们拥有了最大堆。现在我们需要执行以下操作。
将根节点与堆中的最后一个元素交换。
将堆的大小减少 1。（这意味着最大元素已到达最后一个位置，我们不需要考虑该元素）。
重建最大堆，不包括最后一个元素。
重复上述步骤，直到只剩下 1 个元素。
for i in range(n-1, 0, -1): # Swap arr[i], arr[0] = arr[0], arr[i] # Heapify root element heapify(arr, i, 0)
Python 中堆排序的完整程序如下：
def heapify(arr, n, i):
# Find largest among root and children
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 root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ')时间复杂度 - O(n logn)
更新于： 2021年6月11日
362 次查看
广告