0%

堆详解

天道酬勤,地道酬善,人道酬诚,道酬信,业道酬精。

一、概念

  1. 堆是一种经过排序的树形数据结构,每个节点都有一个值,通常我们所说的堆的数据结构是指二叉树,所以堆在数据结构中通常可以被看做是一棵树的数组对象。
  2. 堆需要满足以下两个性质:
    • 堆中某个节点的值总是不大于或不小于其父节点的值(或者说每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值)
    • 堆总是一棵完全二叉树
  3. 分类
    • 最大堆:根节点最大的堆叫做最大堆或大根堆
    • 最小堆:根节点最小的堆叫做最小堆或小根堆
  4. 应用
    • 优先队列
    • 求中位数
    • Top K问题