什么是堆
堆是一种完全二叉树型结构,每个结点都有一个值。
堆的特点
堆满足任意结点始终不大于(或者不小于)左右子结点,其中,前者称为小顶堆,后者为大顶堆。小顶堆又称最小堆,堆顶为最小值,每个父结点都小于孩子结点;大顶堆又称最大堆,堆顶为最大值,每个父结点都大于孩子结点。
堆的应用
是实现优先队列首选的数据结构,解决 TopK 问题、堆排序等。
动手试一试
(提示:点击交互式代码框右上角绿色三角按钮可运行代码)
下面是一个简单的大顶堆实现,先不要关心实现原理,亲自试一试堆的各种操作吧
1. 创建一个堆,并添加几个元素
2. 向已有的堆中插入新元素