分享好友

×
取消 复制
返回小栈
常见数据结构的实现(二):二叉堆
小雨滴2020-05-20 12:04:01

上一篇我讲过了跳跃表的实现,那么这篇文章就是分析二叉堆的实现了。。

鸿胪少卿:常见数据结构的实现(一):跳跃表zhuanlan.zhihu.com图标

介绍

堆也是一种基本的数据结构,分为大根堆和小根堆,实现方式可以有数组和二叉树两种方法。数组实现的优点主要是支持随机访问,缺点就不用多说了。二叉树实现可以很好地适应动态数据变化的情况。堆支持的操作主要有三种: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 = ;
        this.head = null;
        this.tail = null;
        this.order = order;
    }

}
  • order表示节点与其子节点元素之间的关系,对于整型数据,节点的元素不大于两个子节点的元素,则为true。等等
  • 绘制的图中为了简单起见,没有画出子节点指向父节点的parent引用,但是实际设计中考虑了这点

先介绍需要实现的几个基本操作,push、pop操作都依赖于这些操作。

添加、删除元素时,都需要在堆内调整元素之间的关系,可以有两种方式:

  1. 改变节点指向其他节点的引用来调整关系,这个稍微复杂点
  2. 直接交换节点指向元素的引用来实现,非常简单,采用这个
    //交换两个节点保存的元素
    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就是需要被删除的节点,那么节点的前一位置当然就是整个二叉树的最右下的节点了。

在添加操作中,查找节点的后一位置时的操作与上面的情况基本对称,稍微不同的是有两个地方:

  1. 先要查找到节点的后一位置的父节点,再将此父节点与新节点建立关系,最后使tail指向新节点
  2. 向上层查找到第一个是左子节点的节点后,其兄弟节点可能为空,这种情形比较简单,大家可以稍微思考下哈哈

总结上面分析的,这其中还涉及到四个基本操作,分别是向上层查找第一个是左子(右子)节点的节点、向下层查找最左下(右下)的节点,下面先贴出它们的实现:

    //从当前节点开始向上查找第一个左子节点或堆顶节点
    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) >= )//正序并且父节点的元素优先,或者优先级相同
                break;
            if (!order && node.comparable.compareTo(temp.comparable) <= )//逆序并且子节点的元素优先,或者优先级相同
                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) < )//右子节点的元素优先
                    temp = node.right;
                if (node.left != null && node.left.comparable.compareTo(temp.comparable) < )//左子节点的元素优先
                    temp = node.left;
            }else {//逆序
                if (node.right != null && node.right.comparable.compareTo(temp.comparable) > )//右子节点的元素非优先
                    temp = node.right;
                if (node.left != null && node.left.comparable.compareTo(temp.comparable) > )//左子节点的元素非优先
                    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 == ) {//堆为空
            head = node;
        }else {
            tail = next();//堆尾后一个位置的父节点
            //更新引用
            //堆大小为偶数时,新元素是右子节点,为奇数时,是左子节点
            if ((size & 1) == )
                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) == )
                node.parent.left = null;
            else
                node.parent.right = null;
            //调整堆,保持有序
            sink(head);
        }
        size--;
        return node.comparable;
    }

后记

二叉堆的实现相比数组实现来说复杂一些,需要用到一点规律,不过当我们完全掌握了流程之后,其实也很简单。

如果觉得文章某些地方写得不够详细、流畅或者有误的话,那么你可以提出建议。后面我会介绍其他一些常用数据结构的实现,希望大家继续关注哦~~~如果觉得我写的不错的话,那就给这篇文章点个赞吧,谢谢!

福利来了,美图就要一起欣赏~~~

0
0
戳我,来吐槽~