定義
優(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)就到這里了。