526互联

第14章. 堆

发布时间 2023-12-06 20:58:44作者: Ac_c0mpany丶

堆(Heap)

堆(Heap)是一种树状的数据结构(不要跟内存模型中的"堆空间"混淆)，常见的堆实现：

  • 堆的一个重要性质：任意节点的值总是>=(或<=)子节点的值：
    • 如果任意节点的值总是>=子节点的值，称为最大堆、大根堆、大顶堆
    • 如果任意节点的值总是<=子节点的值，称为最小堆、小根堆、小顶堆
  • 最大堆的最大值肯定在根节点处，最小堆的最小值也是在根节点处
  • 由此可见，堆中的元素必须具备可比较性(跟二叉搜索树一样)

堆的接口