堆排序是指利用堆积树（堆）这种数据结构设计的排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引元素。堆分为大根堆和小根堆，是完全二叉树；大根堆的要求是每个节点的值都不大于其父节点的值，A[PARENT[i]]>=A[i]。再数组的非降序排序中，需要使用的是大根堆。跟进大根堆的要求可知，最大的值一定再堆顶。
# -*- coding: utf-8 -*-
"""
下标： 0,1,2,3,4
列表：[2,5,1,9,0]
2*i+1<size
i<(size-1)//2
"""
# 1、构建堆
def maxHeapify(heap, heapSize, root): # 再堆中，做结构调整使得父节点的值大于子节点的值
left = 2 * root + 1
right = left + 1
larger = root
if left < heapSize and heap[larger] < heap[left]:
larger = left
if right < heapSize and heap[larger] < heap[right]:
larger = right
if larger != root: # 如果做了堆调整则larger的值等于左节点或者右节点的，这个时候对调值操作
heap[larger], heap[root] = heap[root], heap[larger]
maxHeapify(heap, heapSize, larger)
# 2、构建排序
def heapSort(heap):
# 构建大顶堆
heapSize = len(heap) # 堆的长度
for i in range((heapSize-1) // 2, -1, -1): # 从后往前出数，从下至上的构建大顶堆
maxHeapify(heap, heapSize, i)
# 将根节点与最后一个元素交换位置，重新调整为大顶堆，分别与后续位置交换
for i in range(len(heap) - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
# 构建局部大顶堆
maxHeapify(heap, i, 0)
return heap
if __name__ == ‘__main__‘:
import numpy as np
li=np.arange(10)
print(li)
heapSort(li)
print(li)
原文：https://www.cnblogs.com/bashliuhe/p/14992155.html