Heap
堆
一個(gè)優(yōu)先級(jí)隊(duì)列栖袋。PriorityQueue便是根據(jù)堆來(lái)實(shí)現(xiàn)的
找出前K個(gè)數(shù)（從大到小）正蛙，構(gòu)建一個(gè)容量為K的小堆督弓，遍歷序列，如果元素比堆頂?shù)脑卮笃寡椋瑒t替換之愚隧，然后下沉，維護(hù)堆锻全。
還有一個(gè)應(yīng)用場(chǎng)景狂塘，堆排序。這都是以前
堆的數(shù)據(jù)存儲(chǔ)鳄厌、增刪改查遍歷操作實(shí)現(xiàn)
堆是一個(gè)完全二叉樹(shù)荞胡，何為完全二叉樹(shù)，1.所有的葉節(jié)點(diǎn)都出現(xiàn)在最下邊兩層了嚎，不就是平衡二叉樹(shù)嗎泪漂。任一兩條路徑的高度差不超過(guò)1。
最大堆：節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值（子節(jié)點(diǎn)之間不一定滿足何種順序）歪泳，因此根節(jié)點(diǎn)是最大的
最小堆：節(jié)點(diǎn)的值小于子節(jié)點(diǎn)的值萝勤，因此根節(jié)點(diǎn)是最小的
堆整體趨勢(shì)上是有序的，但不嚴(yán)格有序呐伞，上一層所有節(jié)點(diǎn)值大于下一層所有節(jié)點(diǎn)的值纵刘，但是一層內(nèi)節(jié)點(diǎn)間是無(wú)序的
堆的數(shù)據(jù)存儲(chǔ)也可以用節(jié)點(diǎn)，和樹(shù)一樣通過(guò)維護(hù)節(jié)點(diǎn)關(guān)系來(lái)維護(hù)荸哟，但是因?yàn)槎咽且粋€(gè)完全二叉樹(shù)的前提假哎，父子節(jié)點(diǎn)間的節(jié)點(diǎn)數(shù)量滿足一定的關(guān)系，所以可以用數(shù)組來(lái)存儲(chǔ)鞍历。找父節(jié)點(diǎn)舵抹、左節(jié)點(diǎn)和右節(jié)點(diǎn)可以通過(guò)計(jì)算數(shù)組下標(biāo)來(lái)獲取。這是可以用數(shù)組來(lái)存儲(chǔ)的必要條件劣砍。如果用節(jié)點(diǎn)關(guān)系的話惧蛹，每個(gè)節(jié)點(diǎn)需要維護(hù)左右節(jié)點(diǎn)和父節(jié)點(diǎn)的引用，增加存儲(chǔ)空間刑枝，二是同一排的節(jié)點(diǎn)之間沒(méi)有直接的引用香嗓，不便于遍歷。所以用數(shù)組存儲(chǔ)各個(gè)節(jié)點(diǎn)装畅。
通過(guò)一個(gè)節(jié)點(diǎn)獲取左靠娱、右、父節(jié)點(diǎn)的下標(biāo)計(jì)算公式推導(dǎo)掠兄。如果獲取前一個(gè)或后一個(gè)直接將下標(biāo)減1或加1即可像云。
定位一個(gè)父節(jié)點(diǎn)，比如在堆中的第c排蚂夕，第l個(gè)迅诬。推導(dǎo)其左節(jié)點(diǎn)下標(biāo)和自己的下標(biāo)關(guān)系。
上圖即為節(jié)點(diǎn)在堆中的位置和映射到數(shù)組的位置關(guān)系婿牍。
一個(gè)標(biāo)準(zhǔn)的堆侈贷，數(shù)字代表節(jié)點(diǎn)在堆中坐標(biāo)，橫坐標(biāo)記為c,縱坐標(biāo)記為l,前提準(zhǔn)備等脂，需要用到等比數(shù)列表達(dá)式和求和公式俏蛮，這里不展開(kāi)。
對(duì)于第c層慎菲，這一層的節(jié)點(diǎn)數(shù)量為,
1到c層總節(jié)點(diǎn)數(shù)量為,推導(dǎo)
嫁蛇、
和
跟
的關(guān)系
N前面的節(jié)點(diǎn)數(shù)量
，則
(下標(biāo)從0開(kāi)始)
N到N左之間的節(jié)點(diǎn)數(shù)量
露该，
可以看出N和N左之間的節(jié)點(diǎn)數(shù)量和N之前的節(jié)點(diǎn)數(shù)量是一樣的睬棚，記為
則
即
通過(guò)父節(jié)點(diǎn)找兩個(gè)子節(jié)點(diǎn)的關(guān)系
則(下標(biāo)從0開(kāi)始)
通過(guò)上面例子，假定父節(jié)點(diǎn)為,則c=3,l=c
計(jì)算得
跟示意圖吻合
通過(guò)子節(jié)點(diǎn)找父節(jié)點(diǎn)解幼，因?yàn)樽庸?jié)點(diǎn)可能是左節(jié)點(diǎn)抑党，也有可能是右節(jié)點(diǎn)。最終我們將要推導(dǎo)出一個(gè)公式撵摆，兩個(gè)子節(jié)點(diǎn)的坐標(biāo)參數(shù)都能計(jì)算出唯一的父節(jié)點(diǎn)坐標(biāo)底靠，先根據(jù)左節(jié)點(diǎn)和右節(jié)點(diǎn)分別求出父節(jié)點(diǎn)的下標(biāo)計(jì)算公式
通過(guò)左節(jié)點(diǎn)
通過(guò)右節(jié)點(diǎn)
備注：此處的計(jì)算結(jié)果按照程序中的除法概念，只取整數(shù)特铝。因?yàn)槎阎袥](méi)有直接維護(hù)節(jié)點(diǎn)間的關(guān)系暑中，對(duì)于任意子節(jié)點(diǎn)壹瘟，無(wú)從得知其是左節(jié)點(diǎn)還是右節(jié)點(diǎn)。所以這個(gè)兩個(gè)公式哪個(gè)可以作為兩種子節(jié)點(diǎn)下標(biāo)計(jì)算父節(jié)點(diǎn)下標(biāo)的通用公式鳄逾？
按照堆是一個(gè)完全二叉樹(shù)設(shè)定稻轨，從第二層開(kāi)始，每一層的節(jié)點(diǎn)數(shù)量都是上一層的2倍雕凹，即每一層的節(jié)點(diǎn)數(shù)都是偶數(shù)殴俱。所以任意一個(gè)右節(jié)點(diǎn)都處于第奇數(shù)個(gè)位置上，即在數(shù)組的下標(biāo)一定是偶數(shù)枚抵，同理得左節(jié)點(diǎn)在數(shù)組中的下標(biāo)一定是奇數(shù)线欲。即，
汽摹。假設(shè)用左節(jié)點(diǎn)的公式來(lái)計(jì)算右節(jié)點(diǎn)下標(biāo)李丰，即
? 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=i_%E5%B7%A6%5C%252%3D1" alt="i_左\%2=1" mathimg="1">，所以竖慧，多加的1作為余數(shù)被丟棄掉了
所以
即可以用左節(jié)點(diǎn)公式來(lái)計(jì)算右節(jié)點(diǎn)下標(biāo)嫌套。
反之，用右節(jié)點(diǎn)公式計(jì)算左節(jié)點(diǎn)圾旨，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=(i_%E5%8F%B3-2)%2F2%5C%252%3D0" alt="(i_右-2)/2\%2=0" mathimg="1">(剛好除盡)踱讨，但是,不能被整除，且整數(shù)減少了1砍的。所以右節(jié)點(diǎn)計(jì)算公式不能計(jì)算左節(jié)點(diǎn)痹筛。
綜上，通過(guò)任意子節(jié)點(diǎn)的下標(biāo)計(jì)算父節(jié)點(diǎn)的下標(biāo)能且只能通過(guò)左節(jié)點(diǎn)公式來(lái)計(jì)算廓鞠。
以上父子節(jié)點(diǎn)下標(biāo)互相計(jì)算公式帚稠，通過(guò)JDK PriorityQueue源碼也能得到印證
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;// 通過(guò)子節(jié)點(diǎn)下標(biāo)計(jì)算父節(jié)點(diǎn)下標(biāo)
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least 通過(guò)父節(jié)點(diǎn)下標(biāo)計(jì)算左節(jié)點(diǎn)下標(biāo)
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
以小頂堆為例
新增操作
先將值追加到堆尾，即放入到數(shù)組的size下標(biāo)處床佳，然后遞歸跟父節(jié)點(diǎn)比較滋早，如果值比父節(jié)點(diǎn)小，則向上篩選砌们，即跟父節(jié)點(diǎn)互換杆麸，代碼實(shí)現(xiàn)如下
private Integer[] queue;
//節(jié)點(diǎn)個(gè)數(shù)
public void add(int value) {
//放入堆底
int k = size;
queue[k] = value;
size++;
if (k == 0) {
return;
}
//向上翻
siftUp(k, value);
}
private void siftUp(int k, int value) {
while (k > 0) {
int parent = (k - 1) >>> 1;//為什么是無(wú)符號(hào)右移
if (queue[parent] == null) {
throw new IllegalArgumentException("parent is null when add " + value);
}
if (value < queue[parent]) {
//對(duì)換
queue[k] = queue[parent];
queue[parent] = value;
//繼續(xù)往上找
k = parent;
}else {
break;
}
}
}
刪除操作
先把最后一個(gè)元素放置在待刪除的位置，然后下調(diào)浪感，直至子節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)都大或者沒(méi)有子節(jié)點(diǎn)了,代碼實(shí)現(xiàn)如下
public boolean remove(int v) {
int p = indexOf(v);
if (p == -1) {
return false;
}
removeAt(p);
return true;
}
private int indexOf(Integer o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
public int removeAt(int i) {
int s = --size;//先得到末尾元素下標(biāo)昔头，同時(shí)將size減1
int value=queue[i];
int v = queue[s];
queue[s] = null;
if (s == i) {//刪除的剛好是末尾這個(gè)元素
return value;
}
//將最后一個(gè)元素放置在待刪除的位置
queue[i] = v;
//下調(diào)操作
siftDown(i);
return value;
}
private void siftDown(int k) {
int half = size >>> 1;
while (k < half) {
//跟子節(jié)點(diǎn)比較
int least= k * 2 + 1;//先假設(shè)較小節(jié)點(diǎn)是左節(jié)點(diǎn)
int c=queue[least];
int right=least+1;
if (right< size && queue[right]<c){
c=queue[right];
least=right;
}
if (queue[k]<c){
break;
}
//交換
queue[least]=queue[k];
queue[k]=c;
k=least;
}
}
遍歷操作
直接遍歷數(shù)組即可。
