|本文
937
字|
需要时间:
3
分钟|
堆是优先队列（Priority Queue）的实现，可以用于 动态选取 一个集合中的最值元素。堆通常指二叉堆，堆包括最大堆和最小堆：最大堆的每一个结点（除了根结点）的值不大于其父结点；最小堆的每一个结点（除了根结点）的值不小于其父结点。
python 有内置堆模块，可以堆list直接操作
import heapq
方法： 堆操作：插入（叶子节点上调），删除（堆顶元素下沉）
堆创建：非叶子节点下沉（从最后一个非叶子节点开始）
最小堆：
最小堆任何一个父节点的值，都小于等于它左右孩子节点的值
创建过程：如果非叶子节点值大于其子节点，将其下沉
最大堆：
最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。
创建过程：如果非叶子节点值小于其子节点，将其下沉
堆排序算法详解+Python实现
-
了解了堆。下面我们来看下堆排序的思想是怎样的(以大根堆为例)：
- 首先将待排序的数组构造出一个大根堆
- 取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆（从堆顶调节就好了）
- 重复第二步，直到这个大根堆的长度为1，此时完成排序。
堆排序的实现
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 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)
# Build a maxheap.
for i in range(n, -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]
heapSort(arr)
n = len(arr)
print ("排序后")
for i in range(n):
print ("%d" %arr[i]),
