堆:
用数组实现的一个完全二叉树,没有父指针和子指针,使用堆属性来排序。
堆属性:
最大堆:父节点的值大于子节点
最小堆:父节点的值小于子节点
堆必须把每一层都占满了才会去启用下一层
父子节点关系:
parent(i) = floor((i - 1)/2) left(i) = 2i + 1 right(i) = 2i + 2
例如:
[10,7,2,5,1]
用处:
构建优先队列
查找最大值或最小值
堆排序
优点:
相比于普通树,占用空间更小
二叉搜索树需要满足平衡才能达到对数的处理速度,而堆不需要整棵树都是有序的。