定義
優(yōu)先隊(duì)列：一種特殊的隊(duì)列统台，隊(duì)列中元素出棧的順序是按照元素的優(yōu)先權(quán)大小，而不是元素入隊(duì)的先后順序柱查。
堆的特性：
- 必須是完全二叉樹(shù)
- 用數(shù)組實(shí)現(xiàn)
-
任一結(jié)點(diǎn)的值是其子樹(shù)所有結(jié)點(diǎn)的最大值或最小值
- 最大值時(shí)掖肋，稱(chēng)為“最大堆”，也稱(chēng)大頂堆逻悠；
- 最小值時(shí)，稱(chēng)為“最小堆”韭脊，也稱(chēng)小頂堆童谒。
可以看到，對(duì)于堆（Heap）這種數(shù)據(jù)結(jié)構(gòu)沪羔，從根節(jié)點(diǎn)到任意結(jié)點(diǎn)路徑上所有的結(jié)點(diǎn)都是有序的饥伊。
堆的ADT
堆的實(shí)現(xiàn)
堆是用數(shù)組實(shí)現(xiàn)的完全二叉樹(shù)，因此在Java中我們可以使用ArrayList實(shí)現(xiàn)，而且向ArrayList中插入元素時(shí)撵渡，當(dāng)數(shù)組容量不足時(shí)融柬，他會(huì)自動(dòng)增長(zhǎng)，這樣也免去考慮堆最大容量的問(wèn)題趋距。這里重點(diǎn)描述以上ADT中插入和刪除的操作粒氧。一般來(lái)說(shuō)，會(huì)從堆中刪除最大值节腐，其實(shí)也就是最大堆中的第一個(gè)元素外盯。下面的實(shí)現(xiàn)為了普適性，實(shí)現(xiàn)了從堆中刪除任一結(jié)點(diǎn)的操作翼雀。
下面就以最大堆的構(gòu)成為例饱苟，研究一下如何使用數(shù)組實(shí)現(xiàn)堆。
最大堆
插入
堆的插入如何實(shí)現(xiàn)呢狼渊？只要我們謹(jǐn)記堆的定義箱熬，實(shí)現(xiàn)起來(lái)其實(shí)是很容易的。這里在回顧一下重點(diǎn)
- 完全二叉樹(shù)
- 任一結(jié)點(diǎn)的值是其左右子樹(shù)的最大值
- 用數(shù)組實(shí)現(xiàn)
考慮下圖所示的堆狈邑。
假設(shè)現(xiàn)有元素60需要插入城须，為了維持完全二叉樹(shù)的特性，新插入的元素一定是放在結(jié)點(diǎn)44的右子樹(shù)米苹；同時(shí)為了滿足任一結(jié)點(diǎn)的值要大于左右子樹(shù)的值這一特性糕伐，新插入的元素要和其父結(jié)點(diǎn)作比較，如果比父結(jié)點(diǎn)大蘸嘶，就要把父結(jié)點(diǎn)拉下來(lái)頂替當(dāng)前結(jié)點(diǎn)的位置良瞧，自己則依次不斷向上尋找，找到比自己小的父結(jié)點(diǎn)就拉下來(lái)训唱，直到?jīng)]有符合條件的值為止褥蚯。這樣，到最后就完成了插入操作况增；總結(jié)一下：
- 新插入的結(jié)點(diǎn)添加到數(shù)組最后
- 和其父結(jié)點(diǎn)比較大小遵岩，如果大于父結(jié)點(diǎn)，就用父結(jié)點(diǎn)替換當(dāng)前位置巡通，同時(shí)自己的位置上移。
- 直到父結(jié)點(diǎn)不再大于自己或者是位置已近到了數(shù)組第一個(gè)位置舍哄，就找到屬于自己的位置了宴凉。
這里為了方便，我們直接占用了數(shù)組下標(biāo)為0的位置表悬，在0的位置放置了一個(gè)null弥锄，這樣數(shù)組中實(shí)際有效值的下標(biāo)就和我們完全二叉樹(shù)中層序遍歷的實(shí)際序號(hào)對(duì)應(yīng)了。這樣，完全二叉樹(shù)中籽暇，如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1温治；換句話說(shuō)，對(duì)于任一結(jié)點(diǎn)n,其父結(jié)點(diǎn)為n/2 取整即可戒悠。
- 初始化堆
public class MaxHeap<T extends Comparable<T>> {
private List<T> mHeap;
public MaxHeap() {
mHeap = new ArrayList<>();
// 為了方便熬荆，數(shù)組下標(biāo)為0 的位置，放置一個(gè)空元素绸狐，使得數(shù)組從下標(biāo)為1的位置開(kāi)始
// 這樣卤恳，完全二叉樹(shù)中，如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1
mHeap.add(0, null);
}
}
當(dāng)然寒矿，為了保證有序性突琳，我們需要堆內(nèi)元素實(shí)現(xiàn)了Comparable接口。
- 插入操作
/**
* 堆的插入操作
* @param value
*/
public void insert(T value) {
//新插入的元素首先放在數(shù)組最后符相，保持完全二叉樹(shù)的特性
mHeap.add(value);
// 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加
int index = mHeap.size() - 1;
// 其父結(jié)點(diǎn)位置
int pIndex = index / 2;
//在數(shù)組范圍內(nèi)拆融，比較這個(gè)插入值和其父結(jié)點(diǎn)的大小關(guān)系，大于父結(jié)點(diǎn)則用父結(jié)點(diǎn)替換當(dāng)前值啊终，index位置上升為父結(jié)點(diǎn)
while (index > 1) {
// 插入結(jié)點(diǎn)小于等于其父結(jié)點(diǎn)镜豹，則不用調(diào)整
if (compare(value, mHeap.get(pIndex)) <= 0) {
break;
} else {
// 依次把父結(jié)點(diǎn)較小的值“降”下來(lái)
mHeap.set(index, mHeap.get(pIndex));
// 向上升一層
index = pIndex;
// 新的父結(jié)點(diǎn)
pIndex = index / 2;
}
}
// 最終找到index 的位置，把值放進(jìn)去
mHeap.set(index, value);
}
/**
*
* @param a
* @param b
* @return a>b 返回值大于0孕索，反之小于0
*/
private int compare(T a, T b) {
return a.compareTo(b);
}
這里需要注意的是逛艰，當(dāng)插入結(jié)點(diǎn)大于父結(jié)點(diǎn)時(shí)，我們并沒(méi)有交換兩個(gè)元素的算法搞旭，而只是把小的元素“降”了下來(lái)散怖，因?yàn)槲覀冏罱K只是想要找到一個(gè)正確的位置而已，交換是不必要肄渗，只需要在最后在合適的位置把值放上去就可以了镇眷。
刪除
理解了插入的實(shí)現(xiàn)，刪除也是遵循同樣的規(guī)則翎嫡。
假設(shè)要從上圖中刪除結(jié)點(diǎn)58，為了維持完全二叉樹(shù)的特性惑申，我們很容易想到用最后一個(gè)元素31去替代這個(gè)58具伍；然后比較31和其子樹(shù)的大小關(guān)系，如果比左右子樹(shù)腥ν铡（如果存在的話）人芽，就要從左右子樹(shù)中找一個(gè)較大的值替換他，而他自己就要跑到對(duì)應(yīng)子樹(shù)的位置绩脆，再次循環(huán)這種操作萤厅，直到?jīng)]有子樹(shù)比他小就可以了橄抹。在這里，按照以上的思路惕味，44將跑到根節(jié)點(diǎn)的位置楼誓，而他的位置將由31替代，堆依然是堆名挥∨备總結(jié)一下：
- 找到要?jiǎng)h除的結(jié)點(diǎn)在數(shù)組中的位置
- 用數(shù)組中最后一個(gè)元素替代這個(gè)位置的元素
- 當(dāng)前位置和其左右子樹(shù)比較，保證符合最大堆的結(jié)點(diǎn)間規(guī)則
- 刪除最后一個(gè)元素
/**
* 堆的任意值的刪除操作
* @param value
* @return
*/
public boolean delete(T value) {
if (mHeap.isEmpty()) {
return false;
}
// 得到數(shù)組中這個(gè)元素的下標(biāo)
int index = mHeap.indexOf(value);
if (index == -1) { // 被刪除元素不在數(shù)組中躺同，即刪除元素不在堆中
return false;
}
// 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加
int lastIndex = mHeap.size() - 1;
T temp = mHeap.get(lastIndex);
// 用最后一個(gè)元素替換被刪除的位置
mHeap.set(index, temp);
int parent;
for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
//當(dāng)前結(jié)點(diǎn)左子樹(shù)下標(biāo)
index = parent * 2;
// 左子樹(shù)下標(biāo)不等于數(shù)組長(zhǎng)度阁猜，因此必然有右子樹(shù) ,則左右子樹(shù)比較大小，這里-1 是因?yàn)閿?shù)組下標(biāo)=1 開(kāi)始
if (index != mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1))<0) {
// 如果右子樹(shù)大蹋艺，則下標(biāo)指向右子樹(shù)
index=index+1;
}
if (compare(temp, mHeap.get(index)) > 0) {
//當(dāng)前結(jié)點(diǎn)大于其左右子樹(shù)剃袍，則不用調(diào)整，直接退出
break;
}else {
// 子樹(shù)上移捎谨，替換當(dāng)前結(jié)點(diǎn)
mHeap.set(parent, mHeap.get(index));
}
}
// parent 就是替換結(jié)點(diǎn)最終該處的位置
mHeap.set(parent, temp);
// 移除數(shù)組最后一個(gè)元素
mHeap.remove(lastIndex);
return true;
}
關(guān)于刪除操作民效，需要注意的一點(diǎn)就是，由于我們的數(shù)組相當(dāng)于是從下標(biāo)=1 的位置開(kāi)始涛救，因此需要注意數(shù)組邊界值和其長(zhǎng)度的關(guān)系畏邢。
下面就來(lái)測(cè)試一下最大堆的實(shí)現(xiàn)：
測(cè)試類(lèi)
private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1, 11, 17};
private static void MaxHeapTest() {
MaxHeap<Integer> mMaxHeap = new MaxHeap<>();
for (int i = 0; i < arrays.length; i++) {
mMaxHeap.insert(arrays[i]);
}
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 17, mMaxHeap.delete(17));
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 1, mMaxHeap.delete(1));
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n", 12, mMaxHeap.delete(12));
mMaxHeap.printHeap();
System.out.printf("insert value %d to maxHeap \n", 16);
mMaxHeap.insert(16);
mMaxHeap.printHeap();
}
printHeap() 的實(shí)現(xiàn)可以參考以下最小堆完整源碼。
輸出：
17 12 5 8 11 3 4 7 1 9 10
delete value 17 from maxHeap isSuccess=true
12 11 5 8 10 3 4 7 1 9
delete value 1 from maxHeap isSuccess=true
12 11 5 8 10 3 4 7 9
delete value 12 from maxHeap isSuccess=true
11 10 5 8 9 3 4 7
insert value 16 to maxHeap
16 11 5 10 9 3 4 7 8
可以看到检吆，當(dāng)我們第一次完成遍歷插入后舒萎，將構(gòu)建出如下所示的一顆完全二叉樹(shù)，很顯然這也是最大堆蹭沛。當(dāng)我們一次刪除元素或插入元素時(shí)臂寝，根據(jù)輸出結(jié)果對(duì)應(yīng)的堆，可以看到我們的插入和刪除操作都是正確的摊灭。
這棵樹(shù)畫(huà)歪了咆贬，湊合看吧，o(╯□╰)o帚呼。
后面幾個(gè)輸出對(duì)應(yīng)的樹(shù)掏缎，感興趣的同學(xué)可以手動(dòng)畫(huà)一下，學(xué)二叉樹(shù)手動(dòng)畫(huà)樹(shù)真是一個(gè)好方法煤杀。
最小堆
最小堆眷蜈，每一個(gè)結(jié)點(diǎn)的值都小于其左右子樹(shù)的值，因此很容易的我們可以想到沈自，在構(gòu)建最大樹(shù)時(shí)把所有判斷大小的邏輯取反就可以實(shí)現(xiàn)了端蛆。事實(shí)上也的確就是這么簡(jiǎn)單，下面給出完整最小堆實(shí)現(xiàn)的完整代碼酥泛，就不具體分析了今豆。
public class MinHeap<T extends Comparable<T>> {
private List<T> mHeap;
//堆內(nèi)當(dāng)前元素個(gè)數(shù)
public int size;
public MinHeap() {
mHeap = new ArrayList<>();
// 為了方便，數(shù)組下標(biāo)為0 的位置柔袁，放置一個(gè)空元素呆躲，使得數(shù)組從下標(biāo)為1的位置開(kāi)始
// 這樣，完全二叉樹(shù)中捶索，如果結(jié)點(diǎn)值為n,那么其左子樹(shù)則為2n,右子樹(shù)為2n+1
mHeap.add(0, null);
}
public void insert(T value) {
//新插入的元素首先放在數(shù)組最后插掂，保持完全二叉樹(shù)的特性
mHeap.add(value);
// 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加，因此最后一個(gè)元素的位置是size-1
int index = mHeap.size() - 1;
// 其父結(jié)點(diǎn)位置
int pIndex = index / 2;
//在數(shù)組范圍內(nèi)腥例，比較這個(gè)插入值和其父結(jié)點(diǎn)的大小關(guān)系辅甥，小于父結(jié)點(diǎn)則用父結(jié)點(diǎn)替換當(dāng)前值，index位置上升為父結(jié)點(diǎn)
while (index > 1) {
// 插入結(jié)點(diǎn)大于等于其父結(jié)點(diǎn)燎竖，則不用調(diào)整
if (compare(value, mHeap.get(pIndex)) >= 0) {
break;
} else {
// 依次把父結(jié)點(diǎn)較大的值“將”下來(lái),把小的值升上去
mHeap.set(index, mHeap.get(pIndex));
// 向上升一層
index = pIndex;
// 新的父結(jié)點(diǎn)
pIndex = index / 2;
}
}
// 最終找到index 的位置璃弄，把值放進(jìn)去
mHeap.set(index, value);
}
public boolean remove(T value) {
if (mHeap.isEmpty()) {
return false;
}
// 得到數(shù)組中這個(gè)元素的下標(biāo)
int index = mHeap.indexOf(value);
if (index == -1) { // 被刪除元素不在數(shù)組中，即刪除元素不在堆中
return false;
}
// 獲取最后一個(gè)元素的在數(shù)組中的索引位置,注意是從index=1的位置開(kāi)始添加构回，因此最后一個(gè)元素的位置是size-1
int lastIndex = mHeap.size() - 1;
T temp = mHeap.get(lastIndex);
// 用最后一個(gè)元素替換被刪除的位置
mHeap.set(index, temp);
int parent;
for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
//當(dāng)前結(jié)點(diǎn)左子樹(shù)下標(biāo)
index = parent * 2;
// 左子樹(shù)下標(biāo)不等于數(shù)組長(zhǎng)度夏块，因此必然有右子樹(shù) ,則左右子樹(shù)比較大小
if (index != mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1))>0) {
// 如果右子樹(shù)小，則下標(biāo)指向右子樹(shù)
index=index+1;
}
if (compare(temp, mHeap.get(index)) < 0) {
//當(dāng)前結(jié)點(diǎn)小于其左右子樹(shù)纤掸，則不用調(diào)整脐供，直接退出
break;
}else {
// 子樹(shù)上移，替換當(dāng)前結(jié)點(diǎn)
mHeap.set(parent, mHeap.get(index));
}
}
// parent 就是替換結(jié)點(diǎn)最終該處的位置
mHeap.set(parent, temp);
// 移除數(shù)組最后一個(gè)元素
mHeap.remove(lastIndex);
return true;
}
private int compare(T a, T b) {
return a.compareTo(b);
}
public void printHeap(){
StringBuilder sb = new StringBuilder();
for(int i=1;i<mHeap.size();i++) {
sb.append(mHeap.get(i)).append(" ");
}
System.out.println(sb.toString());
}
}
測(cè)試類(lèi)就不在這里占篇幅了借跪，有興趣的同學(xué)可以直接看源碼.
好了政己，堆的實(shí)現(xiàn)就到這里了。
