預(yù)備知識(shí)
完全二叉樹(shù)的定義：
若設(shè)二叉樹(shù)的高度為h省有，除第 h 層外患雇，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)前硫，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)

滿(mǎn)二叉樹(shù)特點(diǎn)：
1、深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)
2、所有節(jié)點(diǎn)的度要么為0骤星，要么為2，且所有葉子節(jié)點(diǎn)都在最后一層
完全二叉樹(shù)特點(diǎn)：
1汤善、樹(shù)中所含n個(gè)節(jié)點(diǎn)與滿(mǎn)二叉樹(shù)的節(jié)點(diǎn)編號(hào)一一對(duì)應(yīng)
2、葉子節(jié)點(diǎn)只會(huì)出現(xiàn)在最后兩層票彪，且葉子節(jié)點(diǎn)都是靠左對(duì)齊

使用數(shù)組來(lái)實(shí)現(xiàn)完全二叉樹(shù)時(shí)有以下規(guī)律：
葉子節(jié)點(diǎn)個(gè)數(shù)=floor((n+1)/2) n是元素?cái)?shù)量
父節(jié)點(diǎn)索引=floor((i-1)/2) i是當(dāng)前節(jié)點(diǎn)索引
左子節(jié)點(diǎn)索引=2i+1

堆
堆(heap)红淡，又稱(chēng)為優(yōu)先隊(duì)列(priority queue)，堆并不是隊(duì)列抹镊，在隊(duì)列中锉屈，我們可以進(jìn)行的操作是向隊(duì)列中添加元素和按照元素進(jìn)入隊(duì)列的先后順序取出元素荤傲。而在堆中垮耳，我們不是按照元素進(jìn)入隊(duì)列的先后順序，而是按照元素的優(yōu)先級(jí)取出元素

堆通常是一個(gè)可以被看做一棵 [完全二叉樹(shù)] 的數(shù)組對(duì)象
我們常用的二叉堆就是一顆任意節(jié)點(diǎn)的優(yōu)先級(jí)不小于其子節(jié)點(diǎn)的完全二叉樹(shù)

思考：為什么說(shuō) 堆通常是一個(gè)可以被看做一棵 [完全二叉樹(shù)] 的數(shù)組對(duì)象
二叉樹(shù)相較于數(shù)組更為復(fù)雜遂黍，其結(jié)構(gòu)特點(diǎn)決定所需占用內(nèi)存空間的大小高于數(shù)組

優(yōu)先級(jí)可以是大小比較或其他條件下的比較（因?yàn)橐笤匾獏⑴c比較终佛，所以堆中不允許元素為null）
比如常見(jiàn)的大根堆：任意節(jié)點(diǎn)的值總是≥子節(jié)點(diǎn)的值，小根堆則相反

堆接口的基本設(shè)計(jì)
int size( ); ? 元素的數(shù)量
boolean isEmpty( ); ? 是否為空
void clear( ); ? ?清空堆中所有元素
void add(E element); ? 插入元素
E get( ); ? 獲得堆頂元素
E remove( ); ? 刪除堆頂元素（取出優(yōu)先級(jí)最高的數(shù)據(jù)）
E replace(E element); ? 刪除堆頂元素的同時(shí)插入一個(gè)新元素

以大根堆為例
進(jìn)行各接口的實(shí)現(xiàn)解析

add
插入時(shí)雾家，我們首先將要插入的數(shù)據(jù)放在數(shù)組的尾部铃彰。但是這樣破壞了堆的特性，因此我們需要進(jìn)行調(diào)整芯咧，保證堆的特性
大根堆形成條件：任意節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值牙捉，堆頂節(jié)點(diǎn)的值最大
1、將插入的節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行比較敬飒，若插入節(jié)點(diǎn)值大于父節(jié)點(diǎn)的值（不符合大根堆形成條件）則 他們之間互換位置
2邪铲、若插入節(jié)點(diǎn)小于父節(jié)點(diǎn)的值（符合大根堆形成條件）或已經(jīng)達(dá)到堆頂，則 返回
3无拗、重復(fù)執(zhí)行以上步驟

public void add(E element){
    elementNotNullCheck(element);
    insureCapacity(size+1);
    elements[size++]=elements;
    siftUp(size-1);
}   
private void siftUp(int index){
    E element=elements[index];
    //index必須滿(mǎn)足有父節(jié)點(diǎn)
    while(index>0){
        //父節(jié)點(diǎn)索引Pindex=floor((index-1)/2
        int parentIndex=(index-1)>>1;
        //若插入節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值带到，符合大根堆構(gòu)造條件無(wú)需交換直接返回
        if(compare(elements[parentIndex],element)>=0) break;
        //不符合構(gòu)造條件，節(jié)點(diǎn)位置進(jìn)行互換后繼續(xù)下一輪循從當(dāng)前父節(jié)點(diǎn)向上重新尋找合適的位置
        temp=elements[parentIndex];
        elements[parentIndex]=elements[index];
        elements[index]=temp;
    
        //重新賦值英染，進(jìn)入下一輪循環(huán)揽惹，繼續(xù)向上與父節(jié)點(diǎn)進(jìn)行比較 
        index=parentIndex;  
    }
}

向上尋找合適位置的過(guò)程中被饿，添加節(jié)點(diǎn)經(jīng)過(guò)不斷地循環(huán)上濾在最終找到合適位置時(shí)才進(jìn)行插入，插入節(jié)點(diǎn)并不需要每一次都交換位置搪搏，之前一直是父節(jié)點(diǎn)的在進(jìn)行位置交換狭握，所以可以進(jìn)行優(yōu)化

private void siftUp(int index){
    E element=elements[index];
    //index必須滿(mǎn)足有父節(jié)點(diǎn)
    while(index>0){
        //父節(jié)點(diǎn)索引Pindex=floor((index-1)/2
        int parentIndex=(index-1)>>2;
        //若插入節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值，符合大根堆構(gòu)造條件無(wú)需交換直接返回
        if(compare(elements[parentIndex],element)>=0) break;

        //不符合構(gòu)造條件疯溺，父節(jié)點(diǎn)的位置下移至子節(jié)點(diǎn)
        elements[index]=elements[parentIndex];
        //重新賦值已當(dāng)前父節(jié)點(diǎn)為起點(diǎn)作為子節(jié)點(diǎn)進(jìn)入下一輪循環(huán)哥牍，繼續(xù)向上與新的父節(jié)點(diǎn)進(jìn)行比較
        index=parentIndex;
    }
    //循環(huán)結(jié)束直到找到正確的位置
    elements[index]=element;
}

remove
刪除元素（取出優(yōu)先級(jí)最高的數(shù)據(jù)），因?yàn)槿〕龆阎凶畲笾岛蟊仨氁ＷC不影響堆的構(gòu)造喝检，所以并不只是將堆頂元素直接賦值為null就完事了
大根堆形成條件：任意節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值嗅辣，所以堆頂節(jié)點(diǎn)為最大值
1、將最后一個(gè)索引節(jié)點(diǎn)的值賦給堆頂節(jié)點(diǎn)
2挠说、堆頂節(jié)點(diǎn)的值與子節(jié)點(diǎn)的值進(jìn)行比較澡谭，若堆頂節(jié)點(diǎn)值小于子節(jié)點(diǎn)的值（不符合大根堆形成條件），則他們之間互換位置
3损俭、重復(fù)執(zhí)行以上步驟

public E remove(){
    emptyCheck();

    int root=elements[0];
    elements[0]=elements[--size];
    elements[size]=null;
    siftDown(0);
    return root;
}
private void siftDown(int index){
    int e=elements[index];
    //非葉子節(jié)點(diǎn)的數(shù)量:floor(size/2)
    int critical=size>>2;
    
    //最后一個(gè)葉子節(jié)點(diǎn)的索引 = 非葉子節(jié)點(diǎn)的數(shù)量
    //保證index是非葉子節(jié)點(diǎn)
    while(index<critical){
        //左子節(jié)點(diǎn)索引
        int childIndex = (index << 1) + 1;
        
        //c右子節(jié)點(diǎn)索引:childIndex+1
        if(childIndex+1<size){
            //選出左右子節(jié)點(diǎn)中的最大值
            int child=math.max(elements[childIndex],elements[childIndex+1]);
        }
        //若堆頂節(jié)點(diǎn)值大于子節(jié)點(diǎn)的值蛙奖，符合條件，則返回
        if(compare(child,e)<=0) break;

        //位置互換
        // int temp=child;
        // child=elements[index];
        // elements[index]=temp;
        //堆頂節(jié)點(diǎn)不斷向下尋找合適位置插入的過(guò)程中杆兵，與子節(jié)點(diǎn)不斷地進(jìn)行位置互換
        elements[index]=elements[childIndex];
        index=childIndex;
    }
    //最終找到合適位置
    elements[index]=e;
}

批量建堆
外部接口調(diào)用

public void main(Stirng[] args){
    BinaryHeap<Integer> heap = new BinaryHeap<>();
    heap.add(2);
    heap.add(5);
    heap.add(1);
    heap.add(3);

    int[] data={2,5,1,3}
    BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
    });
}

若想將一段指定的數(shù)據(jù)添加進(jìn)堆中雁仲，然后取出優(yōu)先值，怎么實(shí)現(xiàn)琐脏？
1攒砖、一個(gè)接一個(gè)的進(jìn)行插入
2、直接將數(shù)組扔進(jìn)堆中日裙，批量建堆（堆化）

heapify

public BinaryHeap(E[] elements, Comparator<E> comparator) {
    super(comparator);
    
    if (elements == null || elements.length == 0) {
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    } else {
        size = elements.length;
        int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
        this.elements = (E[]) new Object[capacity];
        for (int i = 0; i < elements.length; i++) {
            this.elements[i] = elements[i];
        }
        heapify();
    }
}

private void heapify() {
    // 自上而下的上濾
    // for (int i = 1; i < size; i++) {
    //  siftUp(i);
    // }
    
    // 自下而上的下濾
    for (int i = (size >> 1) - 1; i >= 0; i--) {
        siftDown(i);
    }
}

批量建堆的過(guò)程可以叫做堆化吹艇，堆化的兩種方式：
1、自上而下的上濾昂拂，上濾操作（葉子節(jié)點(diǎn)與父節(jié)點(diǎn)比較）
2受神、自下而上的下濾，下濾操作（父節(jié)點(diǎn)與葉子節(jié)點(diǎn)比較）
效率分析：
完全二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)量（n/2格侯，n為總節(jié)點(diǎn)數(shù)量）為總結(jié)點(diǎn)的1/2鼻听，若采用方式一，則一半的節(jié)點(diǎn)（最后一層的葉子節(jié)點(diǎn)）需要進(jìn)行上濾

所以采用方式2 效率相對(duì)更高

清空
此處最大堆的結(jié)構(gòu)利用了數(shù)組联四，所以與數(shù)組的清空方式一樣

public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}