常见数据结构的实现（二）：二叉堆
上一篇我讲过了跳跃表的实现，那么这篇文章就是分析二叉堆的实现了。。
介绍
堆也是一种基本的数据结构，分为大根堆和小根堆，实现方式可以有数组和二叉树两种方法。数组实现的优点主要是支持随机访问，缺点就不用多说了。二叉树实现可以很好地适应动态数据变化的情况。堆支持的操作主要有三种：push操作、pop操作、peek操作。
下面的一张图是我自己绘制的二叉堆（小根堆）：
heap.png
分析
按照上面的图，所有节点包含以下属性：存储的元素，指向左子节点的引用，指向右子节点的引用。为了方便，具体实现时每个节点还有一个指向父节点的引用。
那么我们可以如下构建节点类和二叉堆类：
//堆的完全二叉树实现
public class Heap {
private int size;//堆的大小
private TreeNode head;//堆顶节点
private TreeNode tail;//堆尾节点
private final boolean order;//true表示正序，false表示逆序
//节点类
private static class TreeNode{
public Comparable comparable;
private TreeNode left;//左子节点
private TreeNode right;//右子节点
private TreeNode parent;//父节点
public TreeNode(Comparable comparable) {
this.comparable = comparable;
this.left = null;
this.right = null;
this.parent = null;
}
}
public Heap(boolean order) {
this.size = 0;
this.head = null;
this.tail = null;
this.order = order;
}
}
- order表示节点与其子节点元素之间的关系，对于整型数据，节点的元素不大于两个子节点的元素，则为true。等等
- 绘制的图中为了简单起见，没有画出子节点指向父节点的parent引用，但是实际设计中考虑了这点
先介绍需要实现的几个基本操作，push、pop操作都依赖于这些操作。
添加、删除元素时，都需要在堆内调整元素之间的关系，可以有两种方式：
- 改变节点指向其他节点的引用来调整关系，这个稍微复杂点
- 直接交换节点指向元素的引用来实现，非常简单，采用这个
//交换两个节点保存的元素
private void swap(TreeNode one, TreeNode other) {
Comparable comparable = one.comparable;
one.comparable = other.comparable;
other.comparable = comparable;
return;
}
一般情况下，head都指向根节点也就是堆顶节点，tail指向最下一层的最右节点，也就是堆尾节点。但是添加、删除元素后，head一般不会改变，而tail一定会改变。所以添加元素后，tail需要指向原来堆尾节点的后一个位置，删除元素后，tail需要指向原来堆尾节点的前一个位置。这两种情况蕴含了两种操作，也就是查找某个节点的前一位置和后一位置。
比如，在上图中节点14的前一位置是节点13，后一位置是节点15，而节点7的前一位置是节点6，后一位置是节点8。
假如查找节点的前一位置时（在删除操作中），我们可以从完全二叉树的结构中总结出规律：从当前节点开始，向上层查找第一个是右子节点的节点，把它的兄弟节点记为A，然后从A开始沿着右子节点的引用链查找最右下的节点，那么这个节点就是我们需要寻找的节点的前一位置。如果在向上层查找的时候没有节点是右子节点呢？这意味着向上查找的过程是一直沿着整个二叉树的“最左的边”进行的，在上图中就是15、7、3、1、0。这时节点15就是需要被删除的节点，那么节点的前一位置当然就是整个二叉树的最右下的节点了。
在添加操作中，查找节点的后一位置时的操作与上面的情况基本对称，稍微不同的是有两个地方：
- 先要查找到节点的后一位置的父节点，再将此父节点与新节点建立关系，最后使tail指向新节点
- 向上层查找到第一个是左子节点的节点后，其兄弟节点可能为空，这种情形比较简单，大家可以稍微思考下哈哈
总结上面分析的，这其中还涉及到四个基本操作，分别是向上层查找第一个是左子（右子）节点的节点、向下层查找最左下（右下）的节点，下面先贴出它们的实现：
//从当前节点开始向上查找第一个左子节点或堆顶节点
private TreeNode upLeft(TreeNode node) {
TreeNode temp;
while (node.parent != null) {
temp = node.parent;
if (temp.left == node)
break;
node = temp;
}
return node;
}
//从当前节点开始向上查找第一个右子节点或堆顶节点
private TreeNode upRight(TreeNode node) {
TreeNode temp;
while (node.parent != null) {
temp = node.parent;
if (temp.right == node)
break;
node = temp;
}
return node;
}
//以当前节点为根的子树的最左节点
private TreeNode downLeft(TreeNode node) {
while (node.left != null)
node = node.left;
return node;
}
//以当前节点为根的子树的最右节点
private TreeNode downRight(TreeNode node) {
while (node.right != null)
node = node.right;
return node;
}
然后查找节点的后一（前一）位置的操作就很容易写出来了：
//查找堆尾后一个位置的父节点
//堆至少包含一个节点，tail不为null
private TreeNode next() {
TreeNode node = upLeft(tail);//从堆尾开始向上查找第一个左子节点或堆顶节点
if (node == head)//若查找到堆顶节点，则返回其最左子节点
return downLeft(head);
node = node.parent;
return node.right == null ? node : downLeft(node.right);//node.right可能为null
}
//查找堆尾前一个位置的节点
//堆至少包含两个节点，tail不为null
private TreeNode previous() {
TreeNode node = upRight(tail);//从堆尾开始向上查找第一个右子节点或堆顶节点
if (node == head)//若查找到堆顶节点，则返回其最右子节点
return downRight(head);
node = node.parent;
return downRight(node.left);//node.left不为null
}
bubble操作
添加操作总是先将新元素放在新的堆尾节点上，然后根据父子节点元素的关系不断地上浮。比如说，对于整型数据，order为true时，若新节点的元素小于父节点的元素，那么应该将它们保存的元素交换，然后继续判断这个条件直到其不满足为止。
//正序时优先元素上浮或者逆序时非优先元素上浮
private void bubble(TreeNode node) {
TreeNode temp;
while (node.parent != null) {
temp = node.parent;
if (order && node.comparable.compareTo(temp.comparable) >= 0)//正序并且父节点的元素优先，或者优先级相同
break;
if (!order && node.comparable.compareTo(temp.comparable) <= 0)//逆序并且子节点的元素优先，或者优先级相同
break;
swap(node, temp);
node = temp;
}
return;
}
sink操作
删除操作总是先使用堆尾节点的元素替换堆顶节点的元素，然后从堆顶开始不断地下沉，最后返回原来的堆顶元素。对于整型数据，order为true时，若父节点的元素不大于子节点的元素，调整结束。
//正序时非优先元素下沉或者逆序时优先元素下沉
private void sink(TreeNode node) {
TreeNode temp = node;
while (true) {
if (order) {//正序
if (node.right != null && node.right.comparable.compareTo(temp.comparable) < 0)//右子节点的元素优先
temp = node.right;
if (node.left != null && node.left.comparable.compareTo(temp.comparable) < 0)//左子节点的元素优先
temp = node.left;
}else {//逆序
if (node.right != null && node.right.comparable.compareTo(temp.comparable) > 0)//右子节点的元素非优先
temp = node.right;
if (node.left != null && node.left.comparable.compareTo(temp.comparable) > 0)//左子节点的元素非优先
temp = node.left;
}
if (node == temp)//父节点的元素优先级最高或者最低，则结束
break;
swap(node, temp);
node = temp;
}
return;
}
push操作
push操作也就是添加操作，搞明白步骤就清楚了：先查找堆尾节点的后一位置的父节点，然后更新节点之间的引用，最后从新节点开始向上调整堆，即可：
//入堆
//过程：查找堆尾后一个位置的【父节点】，更新引用，调整堆，更新计数
public void push(Comparable comparable) {
TreeNode node = new TreeNode(comparable);
if (size == 0) {//堆为空
head = node;
}else {
tail = next();//堆尾后一个位置的父节点
//更新引用
//堆大小为偶数时，新元素是右子节点，为奇数时，是左子节点
if ((size & 1) == 0)
tail.right = node;
else
tail.left = node;
node.parent = tail;
}
tail = node;
//调整堆，保持有序
bubble(tail);
size++;
return;
}
pop操作
pop操作（删除操作）同理，先查找堆尾节点的前一位置，然后交换元素，更新节点之间的引用，最后从堆顶开始向下调整堆：
//出堆
//限制条件：调用pop()方法前先调用isEmpty()方法判断
//过程：查找堆尾前一个位置的节点，交换元素，更新引用，调整堆，更新计数
public Comparable pop() {
TreeNode node = tail;
if (size == 1) {//只有一个元素
head = null;
tail = null;
}else {
tail = previous();//堆尾前一个位置
swap(head, node);//交换元素
//更新引用
//堆大小为偶数时，堆尾是左子节点，为奇数时，是右子节点
if ((size & 1) == 0)
node.parent.left = null;
else
node.parent.right = null;
//调整堆，保持有序
sink(head);
}
size--;
return node.comparable;
}
后记
二叉堆的实现相比数组实现来说复杂一些，需要用到一点规律，不过当我们完全掌握了流程之后，其实也很简单。
如果觉得文章某些地方写得不够详细、流畅或者有误的话，那么你可以提出建议。后面我会介绍其他一些常用数据结构的实现，希望大家继续关注哦~~~如果觉得我写的不错的话，那就给这篇文章点个赞吧，谢谢！
欣赏美可以使人愉悦~~~
