• 需要实现三种操作:插入、取极大值、删除极大值
  • 需要满足[堆序性]

完全二叉堆

完全二叉堆是相对简单直接的一种堆的实现:

  • 整体形式是一颗满足堆序性完全二叉树
  • 插入:最坏时间复杂度为 ,期望时间复杂度为
  • 删除:最坏和期望时间复杂度均为

Floyd 建堆法,可以在 时间内建成一个完全二叉堆。

锦标赛树

锦标赛树,可用于实现 Top K 排序和多路归并

多叉堆

多叉堆,可以用于优化 Dijkstra 算法中的取最短边环节等,可以在稠密图上保持 时间,在稀疏图上达到 时间(完全二叉堆会退化到

左式堆

左式堆,与 Splay 的思想有相通之处,通过控制右侧藤的长度(保持在 )来控制合并时间