堆和优先队列

堆和优先队列

优先队列:出队顺序和入队顺序无关,和优先级相关;

使用堆这种底层数据结构来实现优先队列,它的时间复杂度最好最坏都是O(log n ),极高的提高了性能

image-20210822202808409

二叉堆

定义:使用二叉树实现的堆;

堆通常是一个可以被看做一棵完全二叉树的数组对象

二叉堆是一颗完全二叉树

image-20210822203336635
特点:
  • 堆中的某个结点的值总是不大于其父节点的值;(最大堆)
堆的时间复杂度
image-20210822225440370
优先对列—自定义优先级
  1. 经典问题,时间复杂度

    • image-20210823095849862
  2. 思路:每次遍历取出元素进行储存,需要剔除最小值,所以需要一个最小堆,取出最小值,剩下的堆就是我们需要的优先队列;

  3. 自定义优先级

    • 自定义一个比较器

    • image-20210823100344450

  4. 具体的函数实现image-20210823101359895

  5. 使用import java.util.PriorityQueue;

    • 因为有比较器接口,直接实现,省去自定义
    • image-20210823111207782

二叉堆的扩展:

  • d叉堆—-时间复杂度为logd(n)image-20210823111528542

  • 索引堆和图论有关(了解)

  • 二项堆和斐波那契堆(了解)

Other:

  • leetcode第347题
-------------本文结束感谢您的阅读-------------