是一个完全二叉树,满足根大于两个儿子(即如有儿子,一定有左儿子,可能有右儿子)。排满这个树的性质保证这个树平衡因子只能是 0 或 1

向上调整:如果这个结点的权值大于它父亲的权值,就交换,向上重复此过程直到不满足或者到根

向下调整:在该结点的儿子中,找一个最大的,与该结点交换,重复此过程直到底层

插入堆:在末尾加入然后向上调整,为

删除:根节点和最后一个节点交换,删除最后一个节点,然后将根节点位置向下调整

建堆

最优的方法是从下到上(从叶子节点到根节点方向),向下调整。这样因为大量节点集中在调整路径短的上面,节省大量时间

叶子节点可以不用调整,从最后的非叶子节点位置开始,节省部分常数

复杂度为