堆的定義
堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個(gè)“優(yōu)秀”的性質(zhì)是兼耀，除了最底層之外艘狭，每一層都是滿的，這使得堆可以利用數(shù)組來(lái)表示（普通的一般的二叉樹通常用鏈表作為基本容器表示）翠订，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素。
如下圖遵倦，是一個(gè)堆和數(shù)組的相互關(guān)系
父子節(jié)點(diǎn)的運(yùn)算關(guān)系
對(duì)于給定的某個(gè)結(jié)點(diǎn)的下標(biāo) i尽超，可以很容易的計(jì)算出這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、孩子結(jié)點(diǎn)的下標(biāo)：
Parent(i) = floor(i/2)梧躺，i 的父節(jié)點(diǎn)下標(biāo)
Left(i) = 2i似谁，i 的左子節(jié)點(diǎn)下標(biāo)
Right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)
最大堆最小堆
二叉堆一般分為兩種：最大堆和最小堆掠哥。
最大堆中的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）
堆中每個(gè)父節(jié)點(diǎn)的元素值都大于等于其孩子結(jié)點(diǎn)（如果存在）
最小堆中的最小元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）
堆中每個(gè)父節(jié)點(diǎn)的元素值都小于等于其孩子結(jié)點(diǎn)（如果存在）
堆排序
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)與末尾的數(shù)交換巩踏，然后將末尾的數(shù)排除大根堆。然后將剩余的堆繼續(xù)調(diào)整為最大堆续搀，再次將堆頂?shù)淖畲髷?shù)與末尾的數(shù)交換塞琼，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束。在堆中定義以下幾種操作：
基本操作
- Bottom-up reheapify (swim).* If the heap order is violated because a node's key becomes larger than that node's parents key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children (one is the old parent, and the other is smaller than the old parent because it was a child of that node) but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root.
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
- Top-down heapify (sink).* If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
- Insert. We add the new item at the end of the array, increment the size of the heap, and then swim up through the heap with that item to restore the heap condition.
-
Remove the maximum. We take the largest item off the top, put the item from the end of the heap at the top, decrement the size of the heap, and then sink down through the heap with that item to restore the heap condition.
Paste_Image.png
實(shí)現(xiàn)
分為兩步禁舷，先建堆再進(jìn)行下沉堆排序彪杉。
建堆過(guò)程是從末尾節(jié)點(diǎn)的孩子開始進(jìn)行下沉(sink)操作，依次執(zhí)行直到頭結(jié)點(diǎn)牵咙，此時(shí)建成大根堆派近。
堆排序則是將頭結(jié)點(diǎn)和尾節(jié)點(diǎn)交換，將尾節(jié)點(diǎn)從堆中刪除洁桌，然后對(duì)頭結(jié)點(diǎn)進(jìn)行下沉操作渴丸。
public void heapSort(int[] array, int n) {
//建堆過(guò)程
for(int i=(array.length-1)/2;i>=0;i--){
sink(array,i,array.length-1);
}
for(int i=n-1;i>0;i--){
swap(array,0,i);
sink(array,0,i-1);
}
}
private void sink(int[] array,int lo,int hi){
while(lo*2+1<=hi){
int left=lo*2+1;
if(left<hi&&array[left]<array[left+1]) left++;
if(array[lo]>=array[left])break;
swap(array,left,lo);
lo=left;
}
}
