堆的概念：

堆（英語：Heap）是計(jì)算機(jī)科學(xué)中的一種特別的樹狀數(shù)據(jù)結(jié)構(gòu)。若是滿足以下特性，即可稱為堆：“給定堆中任意節(jié)點(diǎn) P 和 C，若 P 是 C 的母節(jié)點(diǎn)，那么 P 的值會(huì)小于等于（或大于等于） C 的值”。若母節(jié)點(diǎn)的值恒小于等于子節(jié)點(diǎn)的值，此堆稱為最小堆（英語：min heap）；反之，若母節(jié)點(diǎn)的值恒大于等于子節(jié)點(diǎn)的值，此堆稱為最大堆（英語：max heap）。在堆中最頂端的那一個(gè)節(jié)點(diǎn)，稱作根節(jié)點(diǎn)（英語：root node），根節(jié)點(diǎn)本身沒有母節(jié)點(diǎn)（英語：parent node）。

堆始于 J._W._J._Williams 在 1964 年發(fā)表的堆排序（英語：heap sort），當(dāng)時(shí)他提出了二叉堆樹作為此算法的數(shù)據(jù)結(jié)構(gòu)。堆在戴克斯特拉算法（英語：Dijkstra's algorithm）中亦為重要的關(guān)鍵。

在隊(duì)列中，調(diào)度程序反復(fù)提取隊(duì)列中第一個(gè)作業(yè)并運(yùn)行，因?yàn)閷?shí)際情況中某些時(shí)間較短的任務(wù)將等待很長(zhǎng)時(shí)間才能結(jié)束，或者某些不短小，但具有重要性的作業(yè)，同樣應(yīng)當(dāng)具有優(yōu)先權(quán)。堆即為解決此類問題設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。

特點(diǎn)：

• 二叉堆是一顆完全二叉樹
• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于(不小于)其父節(jié)點(diǎn)的值(最大堆或最小堆)

最大堆

思維導(dǎo)圖：

本章我們將用數(shù)組存儲(chǔ)一個(gè)最大堆，我們先來了解一下數(shù)組索引和堆直接的關(guān)系：

從索引1開始

從索引0開始

區(qū)別只是公式變換一下，但為了不浪費(fèi)數(shù)組單元，我們從索引0開始實(shí)現(xiàn)代碼。

代碼部分：

import com.wk.chapter01.array.DynamicGenericsArray;

public class MaxHeap<E extends Comparable<E>> {
    //使用第一章實(shí)現(xiàn)的動(dòng)態(tài)泛型數(shù)組
    private DynamicGenericsArray<E> arrayheap;

    /**
     * 堆容量為數(shù)組容量
     *
     * @param capacity
     */
    public MaxHeap(int capacity) {
        this.arrayheap = new DynamicGenericsArray<>(capacity);
    }

    /**
     * 默認(rèn)容量為10
     */
    public MaxHeap() {
        this.arrayheap = new DynamicGenericsArray<>();
    }

    //返回元素個(gè)數(shù)
    public int size() {
        return arrayheap.size();
    }

    //堆是否為空
    public boolean isEmpty() {
        return arrayheap.isEmpty();
    }

    //返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的父節(jié)點(diǎn)的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't hava parent");
        }
        return (index - 1) / 2;
    }

    //返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的左孩子節(jié)點(diǎn)的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    //返回完全二叉樹的數(shù)組表示中，一個(gè)索引所表示的元素的右孩子節(jié)點(diǎn)的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }
}

此處我們用到了第一章的動(dòng)態(tài)泛型數(shù)組，且在其中添加了一個(gè)方法，用于交換兩個(gè)索引的數(shù)據(jù)，該方法代碼：

//交換i索引和j索引的數(shù)據(jù)
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("i or j isn't current index");
        }
        E temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

增加元素到堆中：

 //向堆中添加元素
    public void add(E e) {
        arrayheap.addLast(e);
        //上浮該元素
        siftUp(arrayheap.size() - 1);
    }

   //在堆中上浮元素
    private void siftUp(int k) {
        //如果該索引大于0且其父索引的元素小于該索引的元素，交換位置，并將父索引賦給該索引
        while (k > 0 && arrayheap.get(parent(k)).compareTo(arrayheap.get(k)) < 0) {
            arrayheap.swap(k, parent(k));
            k = parent(k);
        }
    }

當(dāng)我們向堆中增加元素時(shí)，把其添加到最后，之后和其父節(jié)點(diǎn)對(duì)比，若其大于父節(jié)點(diǎn)元素，則違反最大堆的定義，需要交換位置，之后將父索引值賦給當(dāng)前索引，繼續(xù)循環(huán)。該操作類似上浮，直到其小于父節(jié)點(diǎn)元素停止該循環(huán)，過程如下圖：

取出堆中的元素:

//看堆中的最大元素
    public E findMax() {
        if (arrayheap.size() == 0) {
            throw new IllegalArgumentException("heap is empty");
        }
        return arrayheap.get(0);
    }

    //取出堆中最大元素
    public E extractMax() {
        E ret = findMax();
        arrayheap.swap(0, arrayheap.size() - 1);
        arrayheap.removeLast();
        siftDown(0);
        return ret;
    }

   //在堆中下沉元素
    private void siftDown(int k) {
        //當(dāng)左孩子索引小于元素個(gè)數(shù)（說明其沒有越界）
        while (leftChild(k) < arrayheap.size()) {
            //先定義i，它的索引等于左孩子
            int i = leftChild(k);
            //從定義可知右孩子索引比左孩子大1，判斷一下右孩子索引是否越界
            //然后我們先比較一下右孩子的值是否大于左孩子，如果成立則將右孩子索引賦值給i
            if (i + 1 < arrayheap.size() && arrayheap.get(i + 1).compareTo(arrayheap.get(i)) > 0) {
                i = rightChild(k);
            }
            //如果當(dāng)前索引的值比其孩子中最大的那個(gè)孩子的值還大，說明到終止條件了，跳出循環(huán)
            if (arrayheap.get(k).compareTo(arrayheap.get(i)) >= 0) {
                break;
            }
            //否則交換它和孩子的位置,并將i賦值給當(dāng)前索引，準(zhǔn)備下一輪循環(huán)
            arrayheap.swap(k, i);
            k = i;
        }
    }

我們?cè)谧畲蠖阎腥〕鲈?，都是取出最大的那個(gè)元素(即頂部的那個(gè)元素)。當(dāng)我們?nèi)〕鲎畲蟮脑睾螅瑢⒆詈笠粋€(gè)元素頂?shù)巾敳?，將其原位置刪除，然后和左右孩子比較，頂部元素肯定是和左右孩子中值最大的那個(gè)交換位置，所以我們得先判斷一下左孩子和右孩子哪個(gè)的值大，得到結(jié)果后將頂部元素和最大的交換位置，具體看下圖，有點(diǎn)繞口呀！

取出最大的元素

將最后一個(gè)元素頂?shù)巾敳?/div>

和左右孩子比較

和值大的孩子交換位置

繼續(xù)和左右孩子比較

交換位置

比較，比孩子大，結(jié)束

取出并替換堆中的最大元素

//找到堆中的最大元素，并且替換成元素e，返回最大元素
    public E replace(E e) {
        E ret = findMax();
        arrayheap.set(0, e);
        siftDown(0);
        return ret;
    }

我們可以通過通過extractMax()先取出堆中的的最大元素，然后在add，但是這樣有2次O(logn)的操作，所以我們這里采用了另一種方法，找到堆中最大元素，直接調(diào)用數(shù)組自帶的set()方法替換，然后通過siftDown()方法將其下沉。

將一組亂序的數(shù)組變成堆：

我們先通過幾個(gè)圖了解步驟：

我們只要將不是葉子節(jié)點(diǎn)的節(jié)點(diǎn)逐個(gè)下沉就行，先從索引大的開始，最后到索引為0的即可。怎么找那個(gè)不是葉子節(jié)點(diǎn)的索引最大的節(jié)點(diǎn)？其實(shí)很簡(jiǎn)單，前面我們知道怎么找一個(gè)孩子的父節(jié)點(diǎn)的公式，這里可以直接用，因?yàn)槲覀冎涝撍饕隙ㄊ亲詈笠粋€(gè)葉子節(jié)點(diǎn)的父節(jié)點(diǎn)。

下沉完成，終止

找索引下的另一個(gè)節(jié)點(diǎn)開始下沉

下沉完成，終止

中間步驟省略，此為完成后的圖

分析結(jié)束，開始代碼部分，我們寫一個(gè)新的構(gòu)造函數(shù)，接收傳入的數(shù)組，先將

DynamicGenericsArray添加一個(gè)新的構(gòu)造函數(shù)

/**
     * 該構(gòu)造函數(shù)用于堆中的將數(shù)組堆化
     * @param arr
     */
    public DynamicGenericsArray(E[] arr) {
        this.array = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            array[i] = arr[i];
        }
        size = arr.length;
    }

然后在我們自己的類中添加新的構(gòu)造函數(shù)

/**
     * 將數(shù)組堆化
     * @param arr
     */
    public MaxHeap(E[] arr) {
        this.arrayheap = new DynamicGenericsArray<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

測(cè)試結(jié)果：

對(duì)一個(gè)不是堆的數(shù)組堆化