堆的定义
堆是一种完全二叉树,它最大的特性是:每个节点的值都大于等于(或小于等于)其子树节点的值。因此堆分为两类:大顶堆和小顶堆。
堆的操作
这两个操作都要用到堆化
插入数据: 插入数据的时候,我们把新插入的数据放到数组的最后,然后从下往上堆化
删除数据: 删除数据的时候,把数组中最后一个元素放到堆顶,然后从上往下堆化。
这两个操作的时间复杂度都是O(logn)
堆的应用
堆排序
建堆:我们将下标从n/2到1的节点,依次进行从上到下的堆化操作,然后就可以将数组中的数据元素组成堆这种数据结构
排序:迭代的将堆顶元素放到堆的末尾,并将堆大小减1,然后再堆化,重复这个过程,直到堆中只剩下一个元素,则数据有序排列了。
优先级队列
求Top K问题。 又可以分为对静态数据和对动态数据的操作。只需利用一个堆就可以高效的做到该问题
求中位数问题(变形:99百分位数据)。
- 处理思路是一样的 利用两个堆,一个大顶堆,一个小顶堆。随着数据的动态添加,动态调整两个堆中的数据,最后大顶堆的堆顶元素就是要求的数据。