一.什么是二叉堆h1>

二叉堆(binary heap)是一种通常用于实现优先队列的数据结构。要想知道二叉堆是什么东西，得从两方面介绍它：结构性和堆序性。

1.结构性

二叉堆是一颗除底层外被完全填满的二叉树，对于底层上的元素满足从左到右填入的特性。如下图所示。

数组上任意位置i上的元素，它的左节点在2i上，右节点在2i + 1上，它的父节点在└i/2┘。不用链表的好处在于，这么做对于计算机来说，访问某一元素的效率很高，不需要遍历即可访问。

2.堆序性

这里我们用最小堆(min-heap)来说明。

在堆中，每个节点n，都小于或等于它的两个子节点。如下图所示。

2.下滤

在我们获取最小元素（即获取根节点并删除它时），我们需要用下滤(percolate down)策略来维护堆序性。

当删除最小元素时，根节点变为空穴，那么为了保证二叉堆的结构性，所以要把最后一个元素x移动到该堆的某个地方。如果x可以直接放入到空穴中，则下滤结束；否则，空穴子节点中最小或最大的值（这要看是min-heap还是max-heap，min-heap为最小值，max-heap为最大值）放入到空穴中，然后空穴下移一位，直到x可以被放置在空穴中。

过程如下图所示。

3.最小二叉堆的Java实现

BinaryHeap.java

BinaryHeapTest.java 测试类

输出：

最小二叉堆实现可用。

以上就是有关二叉堆(binary heap)介绍及其Java实现。

有关[数据结构与算法]的学习内容已经上传到github，喜欢的朋友可以支持一下。
data-structures-and-algorithm-study-notes-java

站在前人的肩膀上前行，感谢以下博客及文献的支持。
《数据结构与算法分析(第3 版) 工业出版 》

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34618 人正在系统学习中