数据结构里的堆是啥意思？看完这篇你就全懂了！

说到堆这个东西，我最早接触的时候，也是一头雾水。看书上说，它是个啥“特殊的数据结构”，可以看成是“一棵树”，但又经常用“数组”来实现。当时我就犯嘀咕，这到底是树还是数组？

后来实际工作中遇到了问题，才逼着自己去把它弄明白。大概是这么个过程：

为啥要折腾它？

主要是当时手头有个活儿，得频繁地从一大堆数据里捞那个最大或者最小的出来。数据还老变，动不动就加塞进来几个，或者删掉几个。

一开始想着用排序，每次变动都重新排一下。试了下，数据量一上来，或者变动太快，那效率简直没法看，卡得要死。普通的列表或者数组，你要找个最大最小的，不得一个个比过去？数据一多，这查找也慢。

动手捣鼓

然后就有人跟我提了“堆”这个东西，说这玩意儿干这个最拿手。我就去捣鼓。看着定义挺简单，不就是个完全二叉树嘛还得满足啥父节点比子节点大（或者小）的规矩。

真正自己动手写起来就不是那么回事了。

• 用数组存，这个想法挺省内存。但父节点和子节点的下标怎么算？左子节点是 `2i + 1`，右子节点是 `2i + 2`（假设数组下标从0开始）？还是教材里那种从1开始存，用 `2i` 和 `2i + 1`？每次都得小心翼翼，生怕搞错一个下标，整个堆的结构就乱套了。
• 往里加数据（插入）咋整？，一般是先塞到数组面，然后让它跟父节点比，如果比父节点大（或小，看是大顶堆还是小顶堆），就交换，一直往上“游”，直到满足堆的性质。这个过程叫“上浮”或者“堆化”啥的。
• 删数据（特别是删顶部的那个最大/最小元素）？更麻烦点。一般是把数组一个元素挪到顶上，替换掉原来的顶，然后让这个新顶跟它的子节点比，如果不满足堆性质，就跟较大的（或较小的）子节点交换，一直往下“沉”，直到找到合适的位置。这个叫“下沉”。
• 还有大顶堆、小顶堆，别搞混了。需求是要最大的，结果你实现成了小顶堆，那就完全反了。这个得一开始就想清楚。

我当时为了搞清楚这些逻辑，在纸上画了好几遍，用小数组模拟了好几次插入和删除的过程，才算是基本捋顺了。

实践中的体会

而且得搞清楚，咱们说的这个数据结构的堆，跟操作系统里内存管理的那个“堆内存”的堆，完全是两码事！别看都叫堆，性质差远了。我刚开始也差点搞混，还以为有啥联系，后来才发现纯粹是名字一样。

后来在一个实时处理任务优先级的场景里，比如要不断处理最高优先级的任务，堆这玩意儿真帮上忙了。新任务来了，按优先级塞进堆里；处理任务时，直接从堆顶取那个优先级最高的。用堆来搞这个“优先队列”，效率确实高，比之前那个傻乎乎的列表加排序好太多了。

但它也不是万能的。它主要就是解决这种动态找最值、维护优先级的场景比较方便。你要是想随机访问里面的某个元素，或者按顺序遍历啥的，那它就不如普通数组或者链表方便了，因为它那个数组里的顺序不是咱们直观的大小顺序。

总结一下

我实践下来的感觉就是，堆这个结构，得知道它的脾气，知道它擅长干它在逻辑上是棵树，物理上常是个数组，核心是维护那个父子大小关系。用对了地方，比如做优先队列、找Top K问题，那是真香；用错了场景，可能还不如老老实实用别的简单结构。反正，多动手写写，模拟一下过程，踩踩坑，自然就明白了。