0


数据结构java版之堆

明天就除夕啦,在这里提前祝大家,新的一年万事胜意

使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。 即用堆来表示就是用完全二叉树来表示。

由图可见,对于非完全二叉树而言,浪费了很多空间。所以堆的表示用的是完全二叉树的表示方法

2.下标关系

①已知双亲(parent)的下:

左孩子(left)下标 = 2 * parent + 1;

右孩子(right)下标 = 2 * parent + 2;

②已知孩子(不区分左右)(child)下标:

双亲(parent)下标 = (child - 1) / 2

二、堆

①堆逻辑上是一棵完全二叉树

②堆物理上是保存在数组中

③满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆

(注意:在整棵树中中的子树均要满足这个条件)

④反之,则是小堆,或者小根堆,或者最小堆(注意:在整棵树中中的子树均要满足这个条件)

⑤ 堆的基本作用是,快速找集合中的最值

体现在下面的操作中

要点:左右子树必须已经是一个堆,才能调整。以大堆举例,最后调整成一棵大根堆的形式

①调整是从最后一棵子树出发的

②每棵子树均是向下调整的

???问题???

①如何找到最后一棵树的子树

前面有提到:(len-1)可以找到最后一棵子树的下标;且

parent=((len-1)-1)/2

②如何遍历

parent--就可以遍历完每棵子树了

③究竟如何实现

用一个向下调整的函数来 实现

④每棵树调整结束的位置如何判定?

每棵树调整的结束位置,实际上都是一样的len

具体实现思路:

代码如下:

public class TestHeap {
    public int []elem;
    //用来记录实际放入数组的元素个数
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }//向下调整
    //parent:每棵树的根结点
    //len:每棵树调整的结束位置
    public void shiftDown(int parent,int len) {
        int child = parent * 2 + 1;
        //该子树至少有一个左孩子
        while (child < len) {
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                //用来保证取的值是当前左右孩子中较大值的下标
                child++;
            }//情况①,elem[c]>elem[p]且p,c需要继续向下检测
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }//情况②,elem[c]<elem[p],其子树也必然为大根堆,所以可以直接退出循环
            else {
                break;
            }
        }
    }
            //创建大根堆
            public void createHeap( int[] array){
                for (int i = 0; i < array.length; i++) {
                    elem[i] = array[i];
                    this.usedSize++;
                }
                for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
                    //向下调整
                    shiftDown(parent, usedSize);
                }
            }
    }

时间复杂度分析:

粗略估算,可以认为是在循环中执行向下调整,为 O(n * log(n)) (了解)实际上是 O(n) 堆排序中建堆过程时间复杂度O(n)怎么来的?

大家可以参考一下这篇文章,这里就不详细解释了

堆排序中建堆过程时间复杂度O(n)怎么来的? - 知乎 (zhihu.com)https://www.zhihu.com/question/20729324

在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次 高的对象。最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话。在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。

这种数据结构就是优先级队列(Priority Queue)

优先级队列的实现方式有很多,但最常见的是使用堆来构建。

解题思路:(实质上为一个向上调整)

①将要入队元素放于该队列的队尾,要是原队列已满的话进行扩容

②找到该节点及其父亲结点,比较两者的值,若elem[child] > elem[parent]即进行交换,反之退出循环

③注意:因为原树已经调节好了,所以此时入队的时候只需要和每棵子树的父亲结点进行比较,循环结束的条件为child<0;

代码:

//向上调整
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
        //此处传入的是下标值,因此注意这里传入的是usedSize-1
        shiftUp(usedSize-1);
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

注意:每次出队列必须保证出最大的或者最小的

解题思路:

①交换0下标和最后一个元素

②调整0下标这棵树即可(向下调整)

代码如下:

 public int poll(){
        if(isEmpty()){
            throw new RuntimeException("此优先队列为空!");
        }int tmp=elem[0];
        elem[0]=elem[usedSize--];
        elem[usedSize--]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
 public int peek(){
        if(isEmpty()){
            throw new RuntimeException("此优先队列为空!");
        }
        return elem[0];
    }

将会在下一节博客中讲述


本文转载自: https://blog.csdn.net/weixin_58850105/article/details/122708870
版权归原作者 反内码者 所有, 如有侵权,请联系我们删除。

“数据结构java版之堆”的评论:

还没有评论