合適的數(shù)據(jù)結(jié)構(gòu)支持兩種操作：刪除最大元素和插入元素

一 API

二 初級實現(xiàn)

2.1 數(shù)組實現(xiàn)（無序）

2.2 數(shù)組實現(xiàn)（有序）

2.3 鏈表表示法

三 堆的定義

四 堆的算法

打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)。這個過程稱為堆的有序化。

4.1 由下至上的堆有序化（上浮）

4.2 由上至下的堆有序化（下沉）

4.3 多叉堆

4.4 調(diào)整數(shù)組大小

4.5 元素的不可變性

4.6 索引優(yōu)先隊列

五 堆排序

堆排序分為兩個階段：在堆的構(gòu)造階段，將原始數(shù)組重新組織進(jìn)一個堆中；

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 在下沉排序階段，我們從堆中按遞減順序取出所有元素并得到排序結(jié) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 果。

5.1 堆的構(gòu)造

5.2 下沉排序

5.3 先下沉后上浮

堆排序是我們所知的唯一能夠同時最優(yōu)地利用空間和時間的方法----在最壞的情況下它也能夠保證使用 ~ 2NlgN次比較和恒定的額外空間。

盡管如此，堆排序的應(yīng)用仍然沒有快速排序廣泛和頻繁，主要是因為：

1.堆排序的內(nèi)循環(huán)比快速排序要復(fù)雜

? ?循環(huán)技術(shù)和各種需要注意的地方較快速排序多

2.堆排序不能有效利用緩存

? ?堆排序載入大數(shù)組時，數(shù)組的引用會很可能布滿整個內(nèi)存，而快速排序是遞歸調(diào)用，保留著很 ? ?多局部的引用，所以快速排序在利用緩存的效率上比堆排序高。

? ?現(xiàn)代機(jī)器的緩存命中率一般都會在 95% 以上，所以有效的利用緩存是很重要的。

? ?快排在遞歸進(jìn)行部分的排序的時候，只會訪問局部的數(shù)據(jù)，因此緩存能夠更大概率的命中；而 ? ?堆排序的建堆過程是整個數(shù)組各個位置都訪問到的，后面則是所有未排序數(shù)據(jù)各個位置都可能 ? ?訪問到的，所以不利于緩存發(fā)揮作用。簡答的說就是快排的存取模型的局部性（locality）更 ? ? ?強(qiáng)，堆排序差一些。

? ?速度和緩存的問題都反映了堆排序讓數(shù)據(jù)過于大距離的移動，你觀察某個元素在整個排序過程 ? ?中的移動過程，會發(fā)現(xiàn)它是前后大幅度的跑動；而快速排序則是盡快的移動到最終的位置，然 ? ?后做小范圍的跳動。

3.同時和歸并排序相比，堆排序是不穩(wěn)定的，在開發(fā)一些要求排序穩(wěn)定性的程序時，顯然應(yīng)該選 ? ?擇歸并排序