allbet代理:自已做动画及编写程序搞清楚最大堆的实现原理

2020-06-29 48 views 0

扫一扫用手机浏览

目录
  • 靠山
  • 观点
  • 最大堆
    • 最大堆的线性存储
    • 动画实现最大堆加入新元素
    • 代码实现最大堆加入新元素
    • 动画实现最大堆取出最大元素
    • 代码实现最大堆取出最大元素
    • 程序测试
  • 最大堆的应用--优先行列
  • 写在最后

靠山

  • 二叉树是数据结构中的重点,也是难点。二叉树比数组、栈、行列等线性结构相比复杂度更高,想要做到心中有“树”,需要自己着手绘图、考察、思索,才气体会其真谛。
  • 在上篇文章《自己着手作图深入明白二叉树、满二叉树及完全二叉树》中,我们对完全二叉树有了一定熟悉,该文将对一种特殊的完全二叉树”最大堆”举行底层研究。

观点

堆(heap)通常是一个可以被看做一棵二叉树的数组工具。堆总是知足下列性子:

  • 堆总是一棵完全二叉树。
  • 堆中某个节点的值总是不大于或不小于其父节点的值;

最大堆

  • 根节点最大的堆叫做最大堆
最大堆的线性存储
  • 由于堆是一种特殊的完全二叉树,可以行使数组聚集形成线性存储的数据结构。
/**
 * 最大堆的底层实现--数组聚集形成线性存储的数据结构
 *  * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的数组聚集
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 获得左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 获得右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 获得父结点索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }
}
动画实现最大堆加入新元素
  • 加入到数组聚集尾部的元素与父结点举行对照,通过上浮操作,保证所有子结点不能大于父结点。
代码实现最大堆加入新元素
/**
 * 最大堆的底层实现
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的数组聚集
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 获得左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 获得右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 获得父结点索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }

    // 添加元素
    public void add(E e) {
        this.list.add(e);
        /**
         * 将加入的结点与父结点举行对照:
         * 若是加入的结点大于父结点,则举行上浮
         * 直至新结点小于或即是父结点为止
         */

        // 获取当前添加元素在数组中的索引
        int i = this.list.size() - 1;
        while (i > 0) {
            E current = this.list.get(i);
            E parent = this.list.get(getParentIndex(i));
            // 若是父结点元素大于当前加入的元素,则举行交流
            if (parent.compareTo(current) < 0) {
                // 交流新加入的结点与父结点的位置
                Collections.swap(this.list, i, getParentIndex(i));
            } else {
                break;
            }
            i = getParentIndex(i);
        }
    }
    
}
动画实现最大堆取出最大元素
  • 获取最大堆中的根结点,即为最大元素;并把尾部结点放置到根结点,并通过下沉操作,把子结点中的最大元素移动根结点。
    allbet代理:自已做动画及编写程序搞清楚最大堆的实现原理 第1张
代码实现最大堆取出最大元素
/**
 * 最大堆的底层实现
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的数组聚集
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 获得左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 获得右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 获得父结点索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }

    // 查找最大元素
    public E findMax() {
        if (this.list.size() == 0) {
            return null;
        }
        // 最大堆中的元素永远在根结点
        return this.list.get(0);
    }

    // 取出最大元素
    public E getMax() {
        if (findMax() != null) {
            E e = findMax();

            /**
             * 取出最大元素后,需要把堆中第二大的元素放置在根结点:
             * 将根结点元素与最后面的元素举行交流,
             * 让最后面的元素出现在根结点,并移除最大元素
             * 将根结点的元素与左右孩子结点对照,直至根结点的元素酿成最大值
             */
            int i = 0;
            Collections.swap(this.list, i, this.list.size() - 1);
            this.list.remove(this.list.size() - 1);

            // 通过循环举行当前结点与左右孩子结点的巨细对照
            while (getLeftChildIndex(i) < this.list.size() && getRightChildIndex(i) < this.list.size()) {
                int leftIndex = getLeftChildIndex(i);
                int rightIndex = getRightChildIndex(i);

                // 通过对照左右孩子的元素哪个较大,确定当前结点与哪个孩子举行交流
                int index = this.list.get(leftIndex).compareTo(this.list.get(rightIndex)) > 0 ? leftIndex : rightIndex;
                if (this.list.get(i).compareTo(this.list.get(index)) < 0) {
                    Collections.swap(this.list, i, index);
                } else {
                    // 若是当前结点都大于左右孩子,则竣事对照
                    break;
                }
                i = index;
            }

            return e;
        } else {
            return null;
        }
    }
}

程序测试
/**
 * 最大堆的底层实现--测试程序
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>();

        // 将10个数字加入形成最大堆
        int[] arrays = {19,29,4,2,27,0,38,15,12,31};
        for (int i = 0; i < arrays.length; i++) {
            maxHeap.add(arrays[i]);
        }

        // 依次从堆中取出最大值
        for (int i = 0; i < arrays.length; i++) {
            System.out.println("第"+(i+1)+"次取出堆现在的最大值:"+maxHeap.getMax());
        }
    }
}

allbet代理:自已做动画及编写程序搞清楚最大堆的实现原理 第2张

最大堆的应用--优先行列

优先行列:出队的和顺序与入队的顺序无关,只与优先级相关;
优先行列通常可以接纳最大堆的数据结构来实现。

/**
 * 用最大堆的数据结构实现优先行列
 * 
 * @author zhuhuix
 * @date 2020-06-28
 */
public class PriorityQueue<E extends Comparable<E>>  {
    private MaxHeap<E> mhp;
    PriorityQueue() {
        mhp=new MaxHeap<>();
    }

    // 入队
    public void enqueue(E e) {
        mhp.add(e);
    }

    // 优选级最高的元素出队
    public E dequeue() {
        return mhp.getMax();
    }

    // 查看优先级最高的元素
    public E getFront() {
        return mhp.findMax();
    }
}

写在最后

  • 以上通过绘图、动画演示、代码编写对堆与最大堆的观点和底层实现方式,都作了深入分析;作为最大堆的反向结构,最小堆的实现也是一样,读者可参考以上动画和代码,着手演习。
  • 绘图、编码不易,请点赞、珍藏、关注三连!!!
,

Allbet Gmaing

欢迎进入欧博Allbet官网(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

Allbet内容转载自互联网,如有侵权,联系Allbet删除。

本文链接地址:http://www.chongqichengbaotoy.com/post/1287.html

相关文章

发表评论