力扣总结 数据结构(七):堆
目录
堆 是一种特别的完全二叉树,每一个节点的值都大于等于或小于等于其孩子节点的值。
堆可以在 O(logN) 时间内插入元素、删除根节点,在 O(1) 时间获得最大值或最小值。一般用于有序弹出元素的场景。
python 中一般直接用内置库 heapq 表示(list 实现的),默认是小顶堆,即堆顶元素是最小值。
额外地,图里面有个重要的 dijkstra 算法常借助堆实现,这里先不涉及。