堆、堆排序

堆的定义

堆是一种完全二叉树,它最大的特性是:每个节点的值都大于等于(或小于等于)其子树节点的值。因此堆分为两类:大顶堆和小顶堆。

堆的操作

这两个操作都要用到堆化

  • 插入数据: 插入数据的时候,我们把新插入的数据放到数组的最后,然后从下往上堆化

  • 删除数据: 删除数据的时候,把数组中最后一个元素放到堆顶,然后从上往下堆化。

这两个操作的时间复杂度都是O(logn)

堆的应用

  1. 堆排序

    • 建堆:我们将下标从n/2到1的节点,依次进行从上到下的堆化操作,然后就可以将数组中的数据元素组成堆这种数据结构

    • 排序:迭代的将堆顶元素放到堆的末尾,并将堆大小减1,然后再堆化,重复这个过程,直到堆中只剩下一个元素,则数据有序排列了。

  1. 优先级队列

  2. 求Top K问题。 又可以分为对静态数据和对动态数据的操作。只需利用一个堆就可以高效的做到该问题

  3. 求中位数问题(变形:99百分位数据)。

    • 处理思路是一样的 利用两个堆,一个大顶堆,一个小顶堆。随着数据的动态添加,动态调整两个堆中的数据,最后大顶堆的堆顶元素就是要求的数据。