HeapSort
轉(zhuǎn)載自：鏈接：http://www.itdecent.cn/p/719b0de606a7 作者：Geek5Nan
侵刪
主要內(nèi)容概述
什么是二叉堆
-
二叉堆的有序化
當(dāng)子節(jié)點(diǎn) > 父節(jié)點(diǎn)
當(dāng)父節(jié)點(diǎn) > 子節(jié)點(diǎn)
二叉堆實(shí)現(xiàn)優(yōu)先隊(duì)列(priority queue)
HeapSort的實(shí)現(xiàn)
什么是二叉堆
一、當(dāng)二叉樹滿足滿足如下條件時(shí)，我們說這個(gè)二叉樹是堆有序的：
- 每一個(gè)父結(jié)點(diǎn)的值都比它的子結(jié)點(diǎn)大（稱為大頂堆）或?。ǚQ為小頂堆）
- 子結(jié)點(diǎn)的大小與其左右位置無關(guān)
二、二叉堆的兩種實(shí)現(xiàn)方式
堆有序的二叉樹，也可稱為二叉堆。
-
二叉堆是最常見的堆結(jié)構(gòu)，因此也常將二叉堆直接稱為堆，可以采用如下兩種方式來表示二叉堆
-
使用指針
- 二叉樹的每個(gè)結(jié)點(diǎn)需存儲(chǔ)三個(gè)指針，分別指向其父結(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)
-
使用數(shù)組
a. indices start at 1 下標(biāo)從1開始
b. Take nodes in level order（層序遍歷）
c. parent of node at k is at k/2
d. children of node at k are 2k and 2k+1
-
-
堆的數(shù)組表示
image
二叉堆的有序化
-
以大頂堆為例，有序化的過程中我們會(huì)遇到兩種情況
在堆底加入一個(gè)較大元素時(shí)，我們需要由下至上恢復(fù)堆的順序
當(dāng)將根結(jié)點(diǎn)替換為一個(gè)較小元素時(shí)，我們需要由上到下恢復(fù)堆的順序
1. 由下至上的堆有序化（上浮-swim）
-
條件：
- 堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變的比它的父結(jié)點(diǎn)更大而被打破
- 即出現(xiàn)子節(jié)點(diǎn)大于父節(jié)點(diǎn)的情況（violation ：子節(jié)點(diǎn)）
-
解決方法(Eliminate the violation)
Exchange key in child with key in parent(將它與它的父結(jié)點(diǎn)交換來恢復(fù)堆有序)
repeat until heap order restored (交換后，這個(gè)結(jié)點(diǎn)比它的兩個(gè)子結(jié)點(diǎn)都大，但這個(gè)結(jié)點(diǎn)仍然可能比它現(xiàn)在的父結(jié)點(diǎn)更大。我們可以一遍遍的用同樣的方式來將其向上移動(dòng)，直到遇到一個(gè)比它更大的父結(jié)點(diǎn)或到達(dá)了堆的根結(jié)點(diǎn))
-
實(shí)現(xiàn)代碼
public static void swim(int k){ while(k > 1 && less(k/2,k)){ exch(k/2,k); k = k/2; } } -
圖示
image -
實(shí)現(xiàn)在堆中插入(Insertion in a heap)
-
Add node at end, then swim it up
public void insert(Key k){ //Key類型實(shí)現(xiàn)Comparable接口 pq[++N] = k; //插入到最后 swim(N); //上浮 }
-
2. 由上至下的堆有序化（下沉-sink）
-
條件
堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變的比它的某個(gè)子結(jié)點(diǎn)更小而被打破
即出現(xiàn)父節(jié)點(diǎn)小于子節(jié)點(diǎn)的情況(violation : 父節(jié)點(diǎn))
-
解決方法(Eliminate the violation)
Exchange key in parent with key in larger child(將它和它的子結(jié)點(diǎn)中較大者交換位置來恢復(fù)堆有序)
Repeat until heap order restored(交換可能會(huì)在子結(jié)點(diǎn)處繼續(xù)打破堆的有序狀態(tài)，此時(shí)可以采用相同的方式，將結(jié)點(diǎn)向下移動(dòng)直到它的子結(jié)點(diǎn)都比它小或是到達(dá)了堆的底部)
-
實(shí)現(xiàn)代碼
public void sink(int k){ while(2 * k <= N){ int j = 2 * k; if(j < N && less(j,j+1)) j++; //j指向較大子節(jié)點(diǎn) if(!less(k,j)) break; //不需要繼續(xù)下沉 exch(k,j); //交換父節(jié)點(diǎn)和較大子節(jié)點(diǎn) k = j; //向下更新k } } -
圖示
image -
實(shí)現(xiàn)在堆中返回最大值
public Key delMax(){ Key max = pq[1]; //保存最大值 exch(1,N--); //交換最后元素到1位置 sink(1); //下沉進(jìn)行堆有序化 pq[N+1] = null; //將最后置為null，實(shí)現(xiàn)刪除 return max; /將最大值進(jìn)行返回 }
二叉堆實(shí)現(xiàn)優(yōu)先隊(duì)列(priority queue)
-
MaxPQ的構(gòu)建
-
public class MaxPQ(Key extends Comparable<Key>>
MaxPQ()——?jiǎng)?chuàng)建一個(gè)優(yōu)先隊(duì)列
MaxPQ(int max)——?jiǎng)?chuàng)建固定大小的優(yōu)先隊(duì)列
MaxPQ(Key[] a)——從給定的數(shù)組中創(chuàng)建優(yōu)先隊(duì)列
void insert(Key k)——插入數(shù)據(jù)
Key max()——返回最大值
Key delMax()——?jiǎng)h除最大值
boolean isEmpty()——判斷隊(duì)列是否為空
int size()——返回當(dāng)前隊(duì)列長(zhǎng)度
-
MaxPQ的實(shí)現(xiàn)
/*
* 此程序是一個(gè)優(yōu)先隊(duì)列(priority queue)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)
* 適用于我們無法保存大量的數(shù)據(jù)時(shí)候
*
* 此時(shí)我們使用的是二叉堆——數(shù)組實(shí)現(xiàn)
* 我們的下標(biāo)是從1-N
*
* 1. 插入數(shù)據(jù)——insert
* 2. 返回最大值
* 3. 判斷隊(duì)列是否空
* 4. 當(dāng)前隊(duì)列長(zhǎng)度
* */
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
//創(chuàng)建固定大小的優(yōu)先隊(duì)列
public MaxPQ(int maxN){
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty() {
return N == 0;
}
//插入數(shù)據(jù)
public void insert(E e) {
//插入到末尾
pq[++N] = e;
//swim
swim(N);
}
//刪除最大值
public Key delMax() throws Exception{
if(isEmpty()) {
throw new Exception("pq is empty");
}
//保存最大值
Key max = pq[1];
//交換最后一個(gè)和最大值
exch(1,N--);
//下沉交換上去的值
sink(1);
pq[++N] = null;
return max;
}
//sink
private void sink(int k) {
// TODO Auto-generated method stub
//將i下沉
while(2 * k <= N) {
int j = 2 * k;
if(j < N && less(j, j+1)) j++; //j指向較大的孩子的下標(biāo)
if(!less(k, j)) break;
exch(k,j); //交換父節(jié)點(diǎn)與較大的子孩子
k = j; //繼續(xù)向下判斷
}
}
//swim
private void swim(int k) {
// TODO Auto-generated method stub
while(k > 1 && less(k/2,k)) { //父小于子，則交換父子
exch(k/2, k);
k = k/2;
}
}
private void exch(int i, int j) {
// TODO Auto-generated method stub
Key tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
}
private boolean less(int i, int j) {
// TODO Auto-generated method stub
return pq[i].compareTo((E) pq[j]) < 0;
}
}
HeapSort的實(shí)現(xiàn)
-
實(shí)現(xiàn)方式
堆排序的過程分為兩步
* Build Heap——?jiǎng)?chuàng)建一個(gè)堆，此時(shí)以大頂堆為例(Heap construction) * repeatedlly move the maximum key——(SortDown)注意的問題是
* 堆的sink操作下標(biāo)是1-N * 而傳入的數(shù)組下標(biāo)是0-N-1 * 需要修改exch和less方法 -
第一步：Build heap using bottom-up method（利用自頂向下創(chuàng)建一個(gè)堆）
因?yàn)槿~子節(jié)點(diǎn)本身就是heap order，因此不需要進(jìn)行排序，因此下標(biāo)從N/2開始
-
代碼實(shí)現(xiàn)
//build heap for(k = N/2; k >= 1;k--) { sink(a,k,N); }
-
第二步:repeatedlly move the maximum key
-
思路
Remove the maximum,one at a time
leave in array, instead of nulling out
-
代碼實(shí)現(xiàn)
//heap sort while(N >= 1) { exch(a,1,N); //交換第一個(gè)和最后一個(gè) sink(a,1,--N); //下沉 }
-
-
HeapSort的實(shí)現(xiàn)
public class HeapSort { public static void sort(Comparable[] a) { int k; int N = a.length; //build heap for(k = N/2; k >= 1;k--) { sink(a,k,N); //此時(shí)的方向是從右向左 } //heap sort while(N >= 1) { exch(a,1,N); sink(a,1,--N); } } private static void sink(Comparable[] a, int k, int N) { // TODO Auto-generated method stub while(2 * k <= N) { //將父節(jié)點(diǎn)與較大的子節(jié)點(diǎn)進(jìn)行交換 int j = 2 * k; if(j < N && less(a,j,j+1)) j++; //j指向較大子節(jié)點(diǎn) if(!less(a,k,j)) break; exch(a,k,j); //交換父節(jié)點(diǎn)和最大子節(jié)點(diǎn) k = j; //k繼續(xù)向下進(jìn)行判斷 } } private static void exch(Comparable[] a, int i, int j) { i--; //因?yàn)槎咽?——N，而數(shù)組是0——N-1 j--; Comparable t = a[i]; a[i] = a[j]; a[j] = t; } private static boolean less(Comparable[] a,int i, int j) { // TODO Auto-generated method stub return a[--i].compareTo(a[--j]) < 0; } } 堆排序圖示
小結(jié)
堆排序算法也是一種選擇排序算法,每一次刪除一個(gè)最大(delMax)或最小(delMin)
整體由堆的構(gòu)建、堆的交換與下沉兩個(gè)步驟組成。
