常见数据结构的实现（二）：二叉堆
上一篇我讲过了跳跃表的实现，那么这篇文章就是分析二叉堆的实现了。。
鸿胪少卿：常见数据结构的实现（一）：跳跃表介绍
堆也是一种基本的数据结构，分为大根堆和小根堆，实现方式可以有数组和二叉树两种方法。数组实现的优点主要是支持随机访问，缺点就不用多说了。二叉树实现可以很好地适应动态数据变化的情况。堆支持的操作主要有三种：push操作、pop操作、peek操作。
下面的一张图是我自己绘制的二叉堆（小根堆）：
分析
按照上面的图，所有节点包含以下属性：存储的元素，指向左子节点的引用，指向右子节点的引用。为了方便，具体实现时每个节点还有一个指向父节点的引用。
那么我们可以如下构建节点类和二叉堆类：
//堆的完全二叉树实现
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 = ;
this.head = null;
this.tail = null;
this.order = order;
}
}相关文章