堆排序
堆排序基本簡(jiǎn)介
1991年的計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者存捺、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發(fā)明了著名的堆排序算法旅挤。
堆排序?qū)儆诒容^排序中的一種链快，具有O(nLgn)的時(shí)間復(fù)雜度栖秕，空間復(fù)雜度為O(1)弧岳。因此堆排序具有空間原址性唬涧，即任何時(shí)候都只需要常數(shù)個(gè)額外的元素空間存儲(chǔ)臨時(shí)數(shù)據(jù)。堆排序利用一種我們稱為“堆”的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序宫补，因此在了解堆排序之前我們需要對(duì)堆這種數(shù)據(jù)結(jié)構(gòu)有個(gè)了解檬姥，才能對(duì)堆排序是如何利用該數(shù)據(jù)結(jié)果完成對(duì)數(shù)據(jù)的排序的。
堆的定義
堆是一個(gè)數(shù)組粉怕，它可以被看成是一個(gè)近似的完全二叉樹健民，樹上的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素。除了最底層外斋荞，該樹是完全充滿的荞雏，而且是從左向右填充虐秦。
堆的一些特性:
堆實(shí)際上是一棵完全二叉樹平酿，根據(jù)完全二叉樹的一些特性我們可以得到父子節(jié)點(diǎn)之間的位置關(guān)系：對(duì)于給定的一個(gè)下標(biāo)為i的節(jié)點(diǎn)我們可以很容計(jì)算到它的父節(jié)點(diǎn)下標(biāo)為i/2 左孩子下標(biāo)為2i,右孩子節(jié)點(diǎn)為2i+1(以上是在下標(biāo)為1開始計(jì)算的，對(duì)于數(shù)組從0開始的計(jì)算作簡(jiǎn)單調(diào)整即可)
最大堆 最小堆
在堆排序中我們把一個(gè)無(wú)序的序列變?yōu)橛行虻倪^程使用的并不是一棵隨意建立的二叉堆悦陋，對(duì)于升序和降序排列分別用到了最大堆以及最小堆蜈彼。因此我們需要了解一下最大堆以及最小堆相對(duì)于普通二叉堆有什么特殊特性：
對(duì)于最大堆中 除了根節(jié)點(diǎn)以外的所有子節(jié)點(diǎn)i都要滿足
A[Parent(i)]>=A[i]
這個(gè)定義表明父節(jié)點(diǎn)的值是不小于其任意的一個(gè)子節(jié)點(diǎn)的值。 因此根節(jié)點(diǎn)存儲(chǔ)的是序列的最大值俺驶，并且任一子樹中幸逆，該子樹所包含的的所有節(jié)點(diǎn)的值都不大于該子樹根節(jié)點(diǎn)的值棍辕。
對(duì)于最小堆則剛好與最大堆相反這里就不在介紹。
了解了最大堆和最小堆我們來(lái)看看堆排序的排序過程还绘。(以下我們利用最大堆來(lái)進(jìn)行排序)
堆排序的過程
- BUILD-MAX-HEAP
- MAX-HEAPIPY
- HEAP-SORT
堆排序由以上三個(gè)步驟分別是建立最大堆楚昭，最大堆維護(hù) 堆排序。
由于BUILD-MAX-HEAP實(shí)際是通過循環(huán)調(diào)用 MAX-HEAPIPY過程來(lái)完成的 因此我們先介紹MAX-HEAPIPY：
MAX-HEAPIPY是用于維護(hù)最大堆性質(zhì)的重要過程拍顷。它的輸入為一個(gè)數(shù)組A和一個(gè)下標(biāo)i抚太，在調(diào)用MAX-HEAPIPY的時(shí)候，我們假定根節(jié)點(diǎn)為L(zhǎng)eft[i]和Right[i]的子樹都是最大堆昔案，但這時(shí)A[i]可能小于其孩子節(jié)點(diǎn)尿贫，這樣就違背了最大堆的性質(zhì)。MAX-HEAPIPY通過讓A[i]的值在堆中“逐級(jí)下降”從而使得以下標(biāo)i為根節(jié)點(diǎn)的子樹重新遵循最大堆的性質(zhì)踏揣。
MAX-HEAPIPY偽代碼如下：
- l = LEFT(i)
- r = RIGHT(i)
- if l <= A.heap-size && A[l] > A [i]
- largest = l;
- else largest = i
- if(r<= A.heap-size && A[r] > A [i]
- largest = r
- if largest != i
- exchange A[i] with A[largest]
- MAX-HEAP(A,largest)
由以上偽代碼可知維護(hù)最大堆性質(zhì)就是將i節(jié)點(diǎn)開始遍歷它的左右子樹庆亡，從未保證i節(jié)點(diǎn)是這棵子樹的最大子節(jié)點(diǎn)，由于在前面的假定中i的子樹已經(jīng)是一棵滿足最大堆的二叉樹因此經(jīng)過MAX-HEAP過程加上i這一層后繼續(xù)滿足最大堆的特性
BUILD-MAX-HEAP 創(chuàng)建最大堆就是將一個(gè)大小n=Array.length的數(shù)組A[0,1...n-1]轉(zhuǎn)換為最大堆的過程捞稿。
用偽代碼表示創(chuàng)建最大堆如下
BUILD-MAX—HEAP(A)
- A.heap-size = A.lenth
- for i = A.length/2 down to 0
- MAX-HEAPRIFY(A,i)
由以上偽代碼可知?jiǎng)?chuàng)建最大堆過程就是從樹的底部向樹的根部遍歷調(diào)用MAX-HEAPRIFY方法來(lái)完成的A.length/2 表示從樹的倒數(shù)第二層開始調(diào)用MAX-HEAP 從底部往上通過循環(huán)逐漸將一棵二叉樹變?yōu)樽畲蠖延帜薄Ｔ谶@個(gè)過程中先是把倒數(shù)第二層的子樹變換為最大堆，然后根據(jù)MAX-HEAP的假定在最底層滿足最大堆后遍歷倒數(shù)第二層時(shí) 這樣遍歷倒數(shù)第三層進(jìn)行MAX-HEAP時(shí)倒數(shù)第三層也滿足了最大堆的特性括享，因此建立最大堆是一個(gè)從底部網(wǎng)上逐級(jí)滿足最大堆的特性搂根，遍歷完根節(jié)點(diǎn)后整棵二叉樹就成為了一棵最大堆。
最后我們來(lái)看HEAP-SORT即堆排序就非常簡(jiǎn)單了
先給出偽代碼
HEAP-SORT(A)
- BUILD-MAX-HEAP(A)
- for(A.length dowm to 1
- exchange A[i] whih A[0]
- MAX-HEAPIFY(A,0)
從以上偽代碼可以看出堆排序是怎么利用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序以及非常巧妙的利用了最大堆的特性非常高效的就將一個(gè)序列變?yōu)榱艘粋€(gè)有序的序列铃辖。
首先是根據(jù)輸入數(shù)組建立一個(gè)最大堆剩愧，根據(jù)最大堆的性質(zhì)此時(shí)序列最大元素就是根節(jié)點(diǎn)的元素，這時(shí)把根節(jié)點(diǎn)移到最后一個(gè)節(jié)點(diǎn)以后娇斩，根節(jié)點(diǎn)的左右子樹仍然滿足最大堆的條件仁卷，這時(shí)在調(diào)用MAX-HEAPIFY就可以很快的讓整棵樹重新成為一棵最大堆。經(jīng)過遍歷和交換過程中A[0]到A[i-1]最大堆 而A[i] 到A[A.length-1]為從小到大排列的數(shù)組,遍歷過程就是不斷的取出處于根節(jié)點(diǎn)的最大元素犬第，然后將剩余元素從未維護(hù)為最大堆的過程锦积。
樣整個(gè)堆排序的過程就介紹完了，了解了堆排序后是不是得感嘆發(fā)明此算法的人是有多聰明呀,想到這么巧妙數(shù)據(jù)構(gòu)歉嗓，和利用該數(shù)據(jù)結(jié)構(gòu)巧妙高效的完成了排序丰介，而我等普通人不是不奢望能發(fā)明算法，但能夠把一種算法理解透并能夠靈活運(yùn)用到實(shí)際的項(xiàng)目中也是不錯(cuò)的了鉴分。
算法復(fù)時(shí)間空間復(fù)雜度分析
- 空間復(fù)雜度
于排序過程是在原數(shù)組上對(duì)元素進(jìn)行處理哮幢，僅僅只是在元素交換時(shí)開辟了常數(shù)個(gè)元素空間，因此堆排序空間復(fù)雜度很簡(jiǎn)單就是O(1)
- 時(shí)間復(fù)雜度
由上面的堆排序的偽代碼可知首先建立最大堆是逐層建立根據(jù)完全二叉樹的性質(zhì)我們很容易得到完全二叉樹的深度為lg(n) 而遍歷一趟的時(shí)間復(fù)雜度為O(n),遍歷趟數(shù)為lg(n)因此堆排序的時(shí)間復(fù)雜度為O(nlgn)
END Talk is cheap show me your code
void maxHeapify(int *unSortArray, int root, int bottom) {
int rootValue = unSortArray[root];
int left = root * 2 + 1;
while (left <= bottom) {
if (left < bottom) {
if (unSortArray[left] < unSortArray[left + 1]) {
left = left + 1;
}
}
if (rootValue < unSortArray[left]) {
unSortArray[root] = unSortArray[left];
root = left;
left = root * 2 + 1;
} else {
left = bottom + 1;
}
}
unSortArray[root] = rootValue;
}
void buildMaxHeap(int *unSortArray, int arraySize) {
for (int i = arraySize / 2 - 1; i >= 0; i--) {
maxHeapify(unSortArray, i, arraySize - 1);
}
}
void heapSortByMaxHeap(int *unSortArray, int arraySize) {
buildMaxHeap(unSortArray, arraySize);
for (int i = arraySize - 1; i >= 0; i--) {
int max = unSortArray[0];
unSortArray[0] = unSortArray[i];
unSortArray[i] = max;
maxHeapify(unSortArray, 0, i - 1);
}
}