数据结构笔记总结(7.2)堆的基础表示

堆的基本结构

在计算机的世界中,通常O(logn)时间复杂度几乎都和树这种数据结构有关。当然不一定我们要显式的构造一棵树,比如排序算法中归并排序、快速排序都是O(nlogn)级别的,排序过程中没有使用树这种数据结构,但是这个递归的过程其实形成了一个隐形的递归树。

二叉堆(Binary Heap)

一个堆本身也是一棵树,堆也有很多种。我们主要学习使用二叉树来表示的一个堆,通常也叫“二叉堆”。二叉堆就是满足一些特殊性质的二叉树。

二叉堆是一颗完全二叉树,但不一定是一棵满二叉树,它不满的那部分一定是在整个树的右下侧。

如果这棵树是一棵满二叉树的话,那么16应该有叶子节点,22和13还应该有左右节点,但是关键是对于一棵满二叉树来说,这棵树有多少层,那么有多少个节点就是固定的。

很多时候元素数量没有这么多个,我们也要把它容纳进一个树的结构中,那应该怎么办?

解决办法就是,每次如果一层容纳不下了的话,在新的一层依次从左到右的顺序来存放节点。

这样就使得对于整棵树来说,最下面一层一定都是叶子节点,其次在叶子节点上面一层可能还有叶子节点,但这些叶子节点一定全在这棵树的右侧

[v_notice]完全二叉树:把元素顺序排列成树的形状。注意与满二叉树区别。[/v_notice]

二叉堆的性质:首先要是完全二叉树,其次堆中某个节点的值总是不大于其父节点的值,这样得到的堆通常叫做“最大堆(相应的可以定义最小堆)”。

最大堆

由于最大堆是一个完全二叉树,具体实现上有一个巧妙的手段,可以使用之前的二分搜素树方式定义一个节点的左右孩子来实现这个堆。

但是完全二叉树特点其实就相当于这一个个节点按顺序一层一层的码放出来,所以可以使用数组的方式来表示完全二叉树。

对于这种方式,其实我们要解决的问题就是对于每一个节点如何找到它的孩子是谁呢?

我们要设置一个节点的话,可以轻易的使用指针去指向相应的左右孩子所在的节点。

但是现在用数组取存储的话,仔细观察是存在这一一个规律的,对于任意一个节点来说,左孩子所在的索引其实是这个节点索引的2倍,右孩子所在的索引是这个节点索引的2倍+1。

当我们使用数组这样表示之后还有一个重要的优势,就是不仅可以方便的索引每个节点的左右孩子,我们还可以非常方便的索引到每个节点的父亲是谁,其实就是i/2,注意是一个整数除法,所以奇数除以2小数抹去。

通常我们习惯索引是从0开始的,因此也可以转换成如下这种方式,公式简单变化一下即可

代码演示

实现最大堆代码 MaxHeap.java

public class MaxHeap> {

    private Array data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(7.2)堆的基础表示

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多