資料結構之二叉堆
一、什麼是二叉堆
二叉堆是一種特殊的堆，二叉堆是完全二進制樹（二叉樹）或者是近似完全二進制樹（二叉樹）。
二叉堆有兩種：最大堆和最小堆。
最大堆：父結點的鍵值總是大于或等于任何一個子節點的鍵值；
最小堆：父結點的鍵值總是小于或等于任何一個子節點的鍵值。
二、二叉堆的基本操作
1.插入
假設在最大堆[90,80,70,60,40,30,20,10,50]種插入85，需要執行的步驟如下：
插入分為兩步：
(1).将data添加到表尾
/*
* 将data插入到二叉堆中
*/
public void insert(T data) {
int size = mHeap.size();
mHeap.add(data); // 将"數組"插在表尾
filterup(size); // 向上調整堆
}
(2).調用向上調整算法
/*
* 最大堆的向上調整算法(從start開始向上直到0，調整堆)
*
* 注：數組實作的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 傳入目前節點的索引start，然後(start-1)/2拿到它父節點的索引，将目前start節點記下來 比較它與父節點的大小，
* 若大于父節點，先将start節點值set為父節點的值，然後兩個指針同步上移，（把父節點指派給目前節點，父節點上移找父節點） 直到走到不滿足start>0
* 将記下來的值set到新start處 參數說明： start -- 被上調節點的起始位置(一般為數組中最後一個元素的索引)
*/
protected void filterup(int start) {
int c = start; // 目前節點(current)的位置
int p = (c - 1) / 2; // 父(parent)結點的位置
T tmp = mHeap.get(c); // 目前節點(current)的大小
while (c > 0) {
int cmp = mHeap.get(p).compareTo(tmp);
if (cmp >= 0)
break;
else {
mHeap.set(c, mHeap.get(p));
c = p;
p = (p - 1) / 2;
}
}
mHeap.set(c, tmp);
}
2.删除
假設從最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要執行的步驟如下：
也是分為兩步：
（1）将data删除，把表尾最後一個元素放上來
/*
* 删除最大堆中的data
*
* 先将data删除，将最後一個元素放上來， 調用向下調算法
*
*
* 傳回值： 0，成功 -1，失敗
*/
public int remove(T data) {
if (mHeap.isEmpty()) {
return -1;
}
int index = mHeap.indexOf(data);
if (index == -1) {
return -1;
}
int size = mHeap.size();
mHeap.set(index, mHeap.get(size - 1));// size-1索引處的值是最後一個元素，将這個元素放到删除元素處
mHeap.remove(size - 1);// 把最後一個元素删除，然後調用向下調整算法
filterdown(index, mHeap.size() - 1);
return 0;
}
（2）調用向下調整算法
/*
* 最大堆的向下調整算法
*
* 注：數組實作的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 從start位置，向下找它最大的孩子，與它自己比較 如果孩子大于它，将此孩子值set到start位置 start下移 反複執行直至條件不滿足
* 最後把初始start處的值set到新位置
*
*
* 參數說明： start -- 被下調節點的起始位置(一般為0，表示從第1個開始) end -- 截至範圍(一般為數組中最後一個元素的索引)
*/
protected void filterdown(int start, int end) {
int c = start; // 目前(current)節點的位置
int l = 2 * c + 1; // 左(left)孩子的位置
T tmp = mHeap.get(c); // 目前(current)節點的大小
while (l <= end) {
int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子
if (l < end && cmp < 0)
l++; // 左右兩孩子中選擇較大者，即mHeap[l+1]
cmp = tmp.compareTo(mHeap.get(l));
if (cmp >= 0)
break; // 調整結束
else {
mHeap.set(c, mHeap.get(l));
c = l;
l = 2 * l + 1;
}
}
mHeap.set(c, tmp);
}
下面是完整代碼：
package priv.qcy.heap;
import java.util.ArrayList;
import java.util.List;
public class MaxHeap<T extends Comparable<T>> {
private List<T> mHeap; // 隊列(實際上是動态數組ArrayList的執行個體)
public MaxHeap() {
this.mHeap = new ArrayList<T>();
}
/*
* 最大堆的向下調整算法
*
* 注：數組實作的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 從start位置，向下找它最大的孩子，與它自己比較 如果孩子大于它，将此孩子值set到start位置 start下移 反複執行直至條件不滿足
* 最後把初始start處的值set到新位置
*
*
* 參數說明： start -- 被下調節點的起始位置(一般為0，表示從第1個開始) end -- 截至範圍(一般為數組中最後一個元素的索引)
*/
protected void filterdown(int start, int end) {
int c = start; // 目前(current)節點的位置
int l = 2 * c + 1; // 左(left)孩子的位置
T tmp = mHeap.get(c); // 目前(current)節點的大小
while (l <= end) {
int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子
if (l < end && cmp < 0)
l++; // 左右兩孩子中選擇較大者，即mHeap[l+1]
cmp = tmp.compareTo(mHeap.get(l));
if (cmp >= 0)
break; // 調整結束
else {
mHeap.set(c, mHeap.get(l));
c = l;
l = 2 * l + 1;
}
}
mHeap.set(c, tmp);
}
/*
* 删除最大堆中的data
*
* 先将data删除，将最後一個元素放上來， 調用向下調算法
*
*
* 傳回值： 0，成功 -1，失敗
*/
public int remove(T data) {
if (mHeap.isEmpty()) {
return -1;
}
int index = mHeap.indexOf(data);
if (index == -1) {
return -1;
}
int size = mHeap.size();
mHeap.set(index, mHeap.get(size - 1));// size-1索引處的值是最後一個元素，将這個元素放到删除元素處
mHeap.remove(size - 1);// 把最後一個元素删除，然後調用向下調整算法
filterdown(index, mHeap.size() - 1);
return 0;
}
/*
* 将data插入到二叉堆中
*/
public void insert(T data) {
int size = mHeap.size();
mHeap.add(data); // 将"數組"插在表尾
filterup(size); // 向上調整堆
}
/*
* 最大堆的向上調整算法(從start開始向上直到0，調整堆)
*
* 注：數組實作的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 傳入目前節點的索引start，然後(start-1)/2拿到它父節點的索引，将目前start節點記下來 比較它與父節點的大小，
* 若大于父節點，先将start節點值set為父節點的值，然後兩個指針同步上移，（把父節點指派給目前節點，父節點上移找父節點） 直到走到不滿足start>0
* 将記下來的值set到新start處 參數說明： start -- 被上調節點的起始位置(一般為數組中最後一個元素的索引)
*/
protected void filterup(int start) {
int c = start; // 目前節點(current)的位置
int p = (c - 1) / 2; // 父(parent)結點的位置
T tmp = mHeap.get(c); // 目前節點(current)的大小
while (c > 0) {
int cmp = mHeap.get(p).compareTo(tmp);
if (cmp >= 0)
break;
else {
mHeap.set(c, mHeap.get(p));
c = p;
p = (p - 1) / 2;
}
}
mHeap.set(c, tmp);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < mHeap.size(); i++)
sb.append(mHeap.get(i) + " ");
return sb.toString();
}
public static void main(String[] args) {
int i;
int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
MaxHeap<Integer> tree = new MaxHeap<Integer>();
System.out.printf("== 依次添加: ");
for (i = 0; i < a.length; i++) {
System.out.printf("%d ", a[i]);
tree.insert(a[i]);
}
System.out.printf("\n== 最 大 堆: %s", tree);
i = 85;
tree.insert(i);
System.out.printf("\n== 添加元素: %d", i);
System.out.printf("\n== 最 大 堆: %s", tree);
i = 90;
tree.remove(i);
System.out.printf("\n== 删除元素: %d", i);
System.out.printf("\n== 最 大 堆: %s", tree);
System.out.printf("\n");
}
}
運作結果：
emmmmm僅供個人複習所用，如有錯誤歡迎指正！