一：堆的介紹
-
Heap是一種數(shù)據(jù)結(jié)構(gòu)具有以下的特點(diǎn)：
1）完全二叉樹(shù)；
2）heap中存儲(chǔ)的值是偏序吴攒； -
Min-heap: 父節(jié)點(diǎn)的值小于或等于子節(jié)點(diǎn)的值；
Max-heap: 父節(jié)點(diǎn)的值大于或等于子節(jié)點(diǎn)的值处渣；
二：堆的操作
-
堆的存儲(chǔ)：
一般都用數(shù)組來(lái)表示堆育叁，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i–1)/2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2愁溜。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2疾嗅。
-
堆的操作：insert
插入一個(gè)元素：新元素被加入到heap的末尾，然后更新樹(shù)以恢復(fù)堆的次序冕象。
每次插入都是將新數(shù)據(jù)放在數(shù)組最后代承。可以發(fā)現(xiàn)從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必然為一個(gè)有序的數(shù)列渐扮，現(xiàn)在的任務(wù)是將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)據(jù)中——這就類似于直接插入排序中將一個(gè)數(shù)據(jù)并入到有序區(qū)間中论悴。
-
堆的操作：Removemax
按定義掖棉，堆中每次都刪除第0個(gè)數(shù)據(jù)。為了便于重建堆膀估，實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)幔亥，然后再?gòu)母Y(jié)點(diǎn)開(kāi)始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最大的察纯，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還大說(shuō)明不需要調(diào)整了帕棉，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過(guò)程饼记。
-
堆的操作：buildHeap 堆化數(shù)組
對(duì)于葉子節(jié)點(diǎn)香伴，不用調(diào)整次序，根據(jù)滿二叉樹(shù)的性質(zhì)具则，葉子節(jié)點(diǎn)比內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)多1.所以i=n/2 -1 即纲，不用從n開(kāi)始。
-
堆排序
堆建好之后堆中第0個(gè)數(shù)據(jù)是堆中最大的數(shù)據(jù)乡洼。取出這個(gè)數(shù)據(jù)再執(zhí)行下堆的刪除操作崇裁。這樣堆中第0個(gè)數(shù)據(jù)又是堆中最大的數(shù)據(jù)，重復(fù)上述步驟直至堆中只有一個(gè)數(shù)據(jù)時(shí)就直接取出這個(gè)數(shù)據(jù)束昵。class Heap { public static void sort(int[] a) { if (a == null || a.length == 0) { return; } int len = a.length; // 構(gòu)建heap for (int i = len / 2 - 1; i >= 0; i--) { down(a, i, len); } // 排序 while (len > 1) { exch(a, 0, len - 1); down(a, 0, len - 1); len--; } } // 向下 private static void down(int[] pq, int k, int len) { while (2 * k + 1 < len) { int j = 2 * k + 1; if (j + 1 < len && less(pq, j, j + 1)) { j++; } if (!less(pq, k, j)) { break; } else { exch(pq, k, j); k = j; } } } public static void show(int[] a) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]); } } private static boolean less(int[] pq, int i, int j) { return pq[i] < pq[j]; } private static void exch(int[] pq, int i, int j) { int temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } }
三：堆的應(yīng)用
//基于heap的優(yōu)先級(jí)隊(duì)列拔稳，N有點(diǎn)問(wèn)題
public class MaxPQ {
private int[] pq;
private int N = 0;
public MaxPQ(int size) {
pq = new int[size];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(int value) {
if (N == pq.length) {
resize(N * 2);
}
pq[N] = value;
swim(N);
N++;
}
public int delMax() {
int max = pq[0];
exch(0, N - 1);
N--;
sink(0);
if (N > 0 && N == pq.length / 4) {
resize(pq.length / 2);
}
return max;
}
// 由下至上的heap有序化
private void swim(int k) {
while (k > 0 && less(pq[(k - 1) / 2], pq[k])) {
exch((k - 1) / 2, k);
k = (k - 1) / 2;
}
}
// 由上至下的heap有序化
private void sink(int k) {
while ((2 * k + 1) < N) {
// 選擇最大的子節(jié)點(diǎn)
int j = 2 * k + 1;
if (j + 1 < N && less(j, j + 1)) {
j = j + 1;
}
if (!less(k, j)) {
break;
} else {
exch(k, j);
k = j;
}
}
}
private void resize(int max) {
int[] temp = new int[max];
for (int i = 0; i < N; i++) {
temp[i] = pq[i];
}
pq = temp;
}
private boolean less(int a, int b) {
return a < b ? true : false;
}
private void exch(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
}
@夢(mèng)工廠
