堆其实是个很简单的数据结构

阅读本文大概需要5分钟

说到堆这种数据结构，很多人的第一反应是感觉很复杂，其实不然，堆就是个优先级队列而已，或者，堆其实就是一种树。本文先讲原理，后面给出堆的实现代码。

优先级队列可以用有序数组来实现，这种做法的问题是，尽管删除最大数据项的时间复杂度为O(1)，但是插入还是需要较长的O(N)时间，这是因为必须移动数组中平均一半的数据项以插入新数据项，并在完成插入后，数组依然有序。

本文主要介绍实现优先级队列的另一种结构：堆。堆是一种树，并非java和C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些，但是插入的时间快的多了。当速度非常重要，且有很多插入操作是，可以选择堆来实现优先级队列。堆有如下特点：

它是完全二叉树。即除了树的最后一层节点不需要是满的外，其他的每一层从左到右都完全是满的。

它常常用一个数组实现。用数组实现的完全二叉树中，节点的索引有如下特点（设该节点的索引为x）：

它的父节点的索引为 (x-1) / 2； 它的左子节点索引为 2x + 1； 它的右子节点索引为 2x + 2。

堆中每个节点的关键字都大于（或等于）这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比，是弱序的。

向堆中插入数据，首先将数据项存放到叶节点中（即存到数组的最后一项），然后从该节点开始，逐级向上调整，直到满足堆中节点关键字的条件为止。

从堆中删除数据与插入不同，删除时永远删除根节点的数据，因为根节点的数据最大，删除完后，将最后一个叶节点移到根的位置，然后从根开始，逐级向下调整，直到满足堆中节点关键字的条件为止。

原理就这么多，堆真的很简单。

下面给出堆的实现代码：

这个实现的代码，可以在等公交的时候、吃饭排队的时候拿来看看，利用碎片化时间来学习。

END

●编号756，输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《18个技术类公众微信》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。