排序_堆排序

内容

1. 默认划分法

代码逻辑

非递归形式

堆排序的应用

堆排序主要服务于优先队列，于是堆排序的应用便是优先队列的应用，用到优先队列的都有堆排序。

1. 优先队列的底层是堆排序，关键部分是从下到上、从上到下调整函数
2. 哈夫曼树
3. 搜索算法，广度搜索，A星算法（每次取出代价最低的方块）
4. 外排序中的败者树是堆的一个变种形式，堆的普通应用是取一个数据，对于败者树来说是取一组数据。
5. 适于找第k数，但是整体性能劣于快速排序方法找第k数，虽然都是按划分寻找的（一半的一半），但是堆排序要把整个都排完，时间复杂度是$O(nlogk)$，而快排找第k数的复杂度是$O(n)$

适用思想的题