下標(biāo)關(guān)系
已知雙親(parent)的下標(biāo)，則：
左孩子(left)下標(biāo) = 2 parent 1;
右孩子(right)下標(biāo) = 2 parent 2;
已知孩子（不區(qū)分左右）(child)下標(biāo),，則：
雙親(parent)下標(biāo) = (child - 1) / 2
堆（heap）
定義：

1. 堆邏輯上是一棵完全二叉樹
2. 堆物理上是保存在數(shù)組中
3. 滿足任意結(jié)點(diǎn)的值都大于其子樹中結(jié)點(diǎn)的值,，叫做大堆，或者大根堆,， 或者最大堆
4. 反之,，則是小堆,，或 者小根堆，或者最小堆
5. 堆的基本作用是,，快速找集合中的最值,。
   向下調(diào)整:時(shí)間復(fù)雜度：O(log(n))
   前提：左右子樹必須已經(jīng)是一個(gè)堆，才能調(diào)整,。
   說明：
6. array 代表存儲(chǔ)堆的數(shù)組
7. size 代表數(shù)組中被視為堆數(shù)據(jù)的個(gè)數(shù)
8. index 代表要調(diào)整位置的下標(biāo)
9. left 代表 index 左孩子下標(biāo)
10. right 代表 index 右孩子下標(biāo)
11. min 代表 index 的最小值孩子的下標(biāo)
    過程（以小堆為例）：
12. index 如果已經(jīng)是葉子結(jié)點(diǎn),，則整個(gè)調(diào)整過程結(jié)束
    1. 判斷 index 位置有沒有孩子
    2. 因?yàn)槎咽峭耆鏄洌瑳]有左孩子就一定沒有右孩子,，所以判斷是否有左孩子
    3. 因?yàn)槎训拇鎯?chǔ)結(jié)構(gòu)是數(shù)組,，所以判斷是否有左孩子即判斷左孩子下標(biāo)是否越界，即 left >= size 越界
13. 確定 left 或 right,，誰是 index 的最小孩子 min
    1. 如果右孩子不存在,，則 min = left
    2. 否則，比較 array[left] 和 array[right] 值得大小,，選擇小的為 min
14. 比較 array[index] 的值 和 array[min] 的值,，如果 array[index] <= array[min]，則滿足堆的性質(zhì),，調(diào)整結(jié)束
15. 否則,，交換 array[index] 和 array[min] 的值
16. 然后因?yàn)?min 位置的堆的性質(zhì)可能被破壞，所以把 min 視作 index,，向下重復(fù)以上過程,。

    //向下調(diào)整成小堆
    public static void shiftDownSmall(int[]array,int size,int index){
    int left=2*index 1;
    while(left<size){
        int right=left 1;
        int min=left;
        while(right<size){
            if(array[left]>array[right]){
                min=right;
            }
            if(array[index]>array[min]){
                swap(array,index,min);
                index=min;
                left=2*index 1;
            }
            else{
                break;
            }
        }
    }
    }
    public static void swap(int array[],int i,int j){
    int t=array[i];
    arrat[i]=array[j];
    array[j]=t; 
    }
    //向下調(diào)整成大堆
    public static void shiftDownBig(int[]a,int i,int s){
    while(2*i 1<s) {
      int m=2*i 1;
      if(m 1<s&&a[m 1]>a[m]){
          m  ;
      }
      if(a[i]>=a[m]){
          break;
      }
      swap(a,i,m);
      i=m;
      } 
    }

向上調(diào)整

****//向上調(diào)整成小端
//直到index=0,執(zhí)行循環(huán)
//找到index的雙親
//比較index和雙親的值，滿足,，調(diào)整結(jié)束,，否則交換，然后讓i=parent繼續(xù)
pubic static void shiftUpSmall(int[]array,int size,int index){
    while (index!=0){
        int parent=(index-1)/2;
        if(array[parent]<=array[index]){
           break;
        }
        swap(array,parent,，index);
        index=parent,；
    }
}
```**

**建堆**

public static void creatHeapBig(int[]array,int size){
for(int i=(s-2)/2;i>=0;i ){
shiftDownBig(a,i,s);
}
}

**優(yōu)先級(jí)隊(duì)列**
* 出隊(duì)列:將[0]位置和[size-1]位置交換，然后做一次向下調(diào)整,。
* 入隊(duì)列(O(logn)):做向上調(diào)整,。
* 返回隊(duì)首元素：即返回[0]下標(biāo)。

public class MyPriorityQueue {
// 不做擴(kuò)容考慮
private int[] array;
private int size;

MyPriorityQueue() {
array = new int[16];
size = 0;
}
//入隊(duì)列
public void offer(int element) {
array[size ] = element;
Heap.shiftUpSmall(array, size - 1);
}
// 出隊(duì)列O(log(n))
public int poll() {
int element = array[0];
array[0] = array[--size];
Heap.shiftDownSmall(array, 0, size);
return element;
}
//取隊(duì)首元素
public int peek() {
// 不做錯(cuò)誤處理
return array[0];
}

**TopK問題**：在海量數(shù)據(jù)中找前k大的數(shù)據(jù)
            找前K個(gè)大的,，建K個(gè)大小的小堆,；
            找前k個(gè)小的，建K個(gè)大小的大堆,；
**堆排序**

public static void heapSort(int[] array){
creatHeapBig(array,array.length);
for(int i=0;i<array.length-1;i ){
//無序[0,array.length-i)
//有序[array.length-i,array.length)
swap(array,i:0,j:array.length-i-1-1);
//無序[0,array.length-i-1)
//長度 array.length-i-1
shiftDownBig(array,i:0,s:array.length-i-1);
}
}