二叉堆是一种二叉树形式的堆数据结构, 是实现优先级队列的常见方式.
结构性质: 二叉堆是完全二叉树.
堆顺序性质: 每个结点的键值大于等于或小于等于子结点们的键值.
在此性质的约束下, 根结点键值为最大值的二叉堆称为最大堆, 根结点键值为最小值的二叉堆称为最小堆.
二叉堆主要有两个基本操作: 插入结点, 删除根结点.
插入结点:
在数组 (二叉堆是隐式数据结构) 的末端插入新结点, 然后自底向上调整 (交换位置) 直到满足堆顺序性质. 时间复杂度为 $O(logn)$.
删除根结点:
先取出根结点, 再将末端结点移到根节点处, 然后自顶向下调整 (交换位置) 直到满足堆顺序性质. 时间复杂度为 $O(logn)$.
二叉堆
来源: http://www.bubuko.com/infodetail-3398799.html