数据结构——堆

堆:

  用数组实现的一个完全二叉树,没有父指针和子指针,使用堆属性来排序。

堆属性:

  最大堆:父节点的值大于子节点

  最小堆:父节点的值小于子节点

  堆必须把每一层都占满了才会去启用下一层

  父子节点关系:

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

例如:

  [10,7,2,5,1]

用处:

  构建优先队列

  查找最大值或最小值

  堆排序

优点:

  相比于普通树,占用空间更小

  二叉搜索树需要满足平衡才能达到对数的处理速度,而堆不需要整棵树都是有序的。

上一篇:FFT 学习笔记


下一篇:树得性质