堆

  • 一个完全二叉树

  • 堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

  • 插入O(logn)

    • 将新的元素放到堆的最后
    • 堆化O(logn)：顺着节点所在路径，向上逐个对比，然后交换

  • 删除堆顶元素O(logn)

    • 删除堆顶元素

    • 将最后一个节点放到堆顶

    • 从上到下堆化（左子树优先）

堆排序

  • 原地

  • 不稳定

  • O(nlogn)

  • 步骤

    • 建堆O(nlogn)[实际是O(n)]

      1. 将数组下标为1的元素看作初始的堆，然后将剩余元素从下往上逐个对比，加入堆中

      2. 完全二叉树的n/2+1到n个节点是叶子节点（根节点下标设为1，方便实现），所以将从n到1的节点逐个从上往下堆化

    • 排序O(nlogn)：不断删除堆顶元素并堆化，直到堆空

优先队列

优先队列的概念和堆的特性十分契合，往优先队列中插入一个元素就相当于往堆中插入一个元素；从优先队列中取出优先级最高的元素，就相当于取出堆顶元素

  • 合并小文件：假设有100个有序的小文件，希望将它们合并成一个有序的大文件，就可以使用大小为100的优先队列。从100个文件中取首字符放入优先队列，每次将堆顶元素放入大文件并再从对应小文件中取出一个字符

  • 高性能定时器：假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。使用优先队列得出最先要执行的任务P，将定时器时间设为P执行时间，就不必轮询了

  • 求TOP K

    • 静态数据：从堆顶删除K个元素

    • 动态数据：维护一个一个大小为K的小顶堆，每当有数据要插入时先于堆顶元素比较，若大于堆顶元素则删除堆顶元素并且将这个数据插入堆中；如果小于堆顶元素小则不做处理。这样无论任何时候需要查询当前K大元素，都能立即返回

  • 求动态数据集合中的n%分位数（以求50%分位数，即中位数为例）

    • 维护一个大顶堆存储前半部分数据，一个小顶堆存储后半部分数据

    • 偶数情况n/2个存大顶堆，n/2存小顶堆；奇数情况n/2+1个存大顶堆，n/2个存小顶堆

    • 如果新加入数据小于等于大顶堆堆顶元素，那么将其加入大顶堆，否则加入小顶堆

    • 数据加入后可能出现两边数据与约定数量不符的情况，这时可以将数据互相移动，将数量满足约定

版权声明：本文为codespoon原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/codespoon/p/13266319.html