堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
二叉堆本质上是一种完全二叉树，它分为两个类型：最大堆和最小堆。最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。二叉堆的根节点叫做堆顶。最大堆和最小堆的特点，决定了在最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。
算法描述
动图演示
代码实现
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
n = len(nums)
if not nums or n==0: return []
# 初始化建立大顶堆
for i in range(n//2-1, -1, -1):
self.maxHeapify(nums, n, i)
# 取出堆顶元素
for i in range(n-1, -1, -1):
temp = nums[0]
nums[0] = nums[i]
nums[i] = temp
self.maxHeapify(nums, i, 0)
return nums
def maxHeapify(self, nums, length, i):
left, right = 2*i+1, 2*i+2
largest = i
if left < length and nums[left] > nums[largest]:
largest = left
if right < length and nums[right] > nums[largest]:
largest = right
if largest != i:
temp = nums[i]
nums[i] = nums[largest]
nums[largest] = temp
self.maxHeapify(nums, length, largest)使用python内置的堆数据结构来排序：
import heapq
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
heap, res = [], []
for i in nums:
heapq.heappush(heap,i)
while heap:
res.append(heapq.heappop(heap))
return res算法特性