数据结构简介:堆---------二叉堆
数据结构简介
二叉堆
1. 定义
二叉堆是完全二叉树或者是近似完全二叉树.
2. 时间复杂度
平均O(logN)
3. 二叉堆特性
- 结构特性:是一颗完全二叉树
- 堆序特性:父节点大于或等于其各子节点(最大堆);父节点小于或等于其各子节点(最小堆)
4. 堆常用操作
- 建堆:
- 将N项插入堆中:执行N次插入操作,采用上浮策略
- 将N项任意放入一颗空树中:放入完成后,从最后一个非叶子节点开始执行下浮操作
- 插入:在尾部插入,采用上浮策略
- 删除最值:删除根节点,将最后一个节点放到根节点位置,采用下浮策略
- 堆其他操作(以最小堆为例)
- 降低关键字的值:采用上浮策略
- 增加关键字的值:采用下浮策略
- 删除除堆中的某个关键字:先执行1,降低无穷大的差值,再执行删除最值操作