自已做動畫及編寫程序搞清楚最大堆的實現原理 | 心目中最理想的車子-發燒車訊

背景
概念
最大堆
- 最大堆的線性存儲
- 動畫實現最大堆加入新元素
- 代碼實現最大堆加入新元素
- 動畫實現最大堆取出最大元素
- 代碼實現最大堆取出最大元素
- 程序測試
最大堆的應用–優先隊列
寫在最後

背景

二叉樹是數據結構中的重點，也是難點。二叉樹比數組、棧、隊列等線性結構相比複雜度更高，想要做到心中有“樹”，需要自己動手畫圖、觀察、思考，才能領會其真諦。
在上篇文章《自己動手作圖深入理解二叉樹、滿二叉樹及完全二叉樹》中，我們對完全二叉樹有了一定認識，該文將對一種特殊的完全二叉樹”最大堆”進行底層研究。

概念

堆（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);
        }
    }
    
}

動畫實現最大堆取出最大元素

獲取最大堆中的根結點，即為最大元素；並把尾部結點放置到根結點，並通過下沉操作，把子結點中的最大元素移動根結點。

代碼實現最大堆取出最大元素

/**
 * 最大堆的底層實現
 *
 * @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());
        }
    }
}

最大堆的應用–優先隊列

優先隊列:出隊的和順序與入隊的順序無關,只與優先級相關；
優先隊列通常可以採用最大堆的數據結構來實現。

/**
 * 用最大堆的數據結構實現優先隊列
 * 
 * @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();
    }
}

寫在最後

以上通過畫圖、動畫演示、代碼編寫對堆與最大堆的概念和底層實現方式，都作了深入分析；作為最大堆的反向結構，最小堆的實現也是一樣，讀者可參考以上動畫和代碼，動手練習。
畫圖、編碼不易，請點贊、收藏、關注三連！！！

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

※超省錢租車方案