侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

解决 TopK 问题的利器(上):堆和堆的构建

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 80 阅读 / 636 字

什么是堆

堆是一种特殊的二叉树,具备以下特性:

堆是一个完全二叉树
每个节点的值都必须大于等于(或小于等于)其左右孩子节点的值
如果每个节点的值都大于等于左右孩子节点的值,这样的堆叫大顶堆;如果每个节点的值都小于等于左右孩子节点的值,这样的堆叫小顶堆。

1.png

上图中,左侧的堆是大顶堆,右侧的堆是小顶堆,我们还可以得出这个结论:对应大顶堆,堆顶一定是最大值;对于小顶堆,堆顶一定是最小值。

如何构建堆

我们在介绍二叉树的定义和存储的时候说到,由于完全二叉树的特殊性,可以通过数组来存储,堆也是完全二叉树,所以我们完全可以通过数组来存储。在使用数组存储堆的时候,把第一个索引位置留空,从第二个索引位置开始存储堆元素,这样,对于索引值为 i 的元素而言,其子节点索引分别为 2i 和 2i+1。

下面我们就来看如何在堆中插入新节点,以大顶堆为例,从叶子结点插入,如果比父级元素大,则与父级元素交换位置,依次类推,直到到达根节点(小顶堆恰好相反):

1.png

注:构建堆的过程叫堆化。

0

评论区