堆 需要实现三种操作:插入、取极大值、删除极大值 需要满足[堆序性] 完全二叉堆 完全二叉堆是相对简单直接的一种堆的实现: 整体形式是一颗满足堆序性的完全二叉树 插入:最坏时间复杂度为 O(logn),期望时间复杂度为 O(1) 删除:最坏和期望时间复杂度均为 O(logn) Floyd 建堆法,可以在 O(n) 时间内建成一个完全二叉堆。 锦标赛树 锦标赛树,可用于实现 Top K 排序和多路归并 多叉堆 多叉堆,可以用于优化 Dijkstra 算法中的取最短边环节等,可以在稠密图上保持 O(e) 时间,在稀疏图上达到 O(nlogn) 时间(完全二叉堆会退化到 O(n2)) 左式堆 左式堆,与 Splay 的思想有相通之处,通过控制右侧藤的长度(保持在 O(logn))来控制合并时间