是一种特殊的树。满足下面这两点要求
- 堆是一个完全二叉树；
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
第二点，也可以换种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。如下图
image.png
1、2大顶堆，根最大数越往下越小3是小顶堆，根最小越往下越大。4不属于完全二叉树
堆排序O(nlogn)
堆排序可以分为建堆和排序
建堆
建堆有2种方法从上到下或从下到上
排序
堆排序
简单点说就是堆顶是最大数，把堆顶放到最后的位置。然后进行“堆化”，循环此动作，最后完成排序
堆化：堆化就是把不符合堆特性的堆进行调整，让其重新满足堆的特性
快速排序，平均情况下，它的时间复杂度为 O(nlogn)。堆排序时间复杂度也是 O(nlogn)，甚至堆排序比快速排序的时间复杂度还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好，这是为什么呢？
首先堆排序的不稳定性，从如一组有序数字，经过建堆后反而无序了，而且堆在频繁交换位置，当排序堆化时也是跳跃访问下标，效率也没有顺序访问好。
堆常见应用
定时器
可以利用小顶堆的特性做定时器，最先开始的时间在堆顶。用当前时间减堆顶时间，时间到了之后执行就可以，这样就省去了时间没到不停循环的资源浪费。
求 Top K
可以利用小顶堆，比如取前5，就创建一个大小为5的小顶堆，遍历数据。如果数大于堆顶就删除堆顶，后把新数插入堆顶堆化。
不同在哪呢，快排是先把分治思想左边小右边大然后在进行最后。堆直接堆化就可以。
网友评论