堆排序

(二叉)堆是一個數(shù)組，它可以被看成一個近似的完全二叉樹。樹上的每一個結(jié)點對應(yīng)數(shù)組中的一個元素。除了最底層外，該樹是完全充滿的，而且是從左像右填充。

在堆排序中，我們使用的是最大堆。最小堆通常用于構(gòu)造優(yōu)先隊列。

在最大堆中，最大堆性質(zhì)是指除了根以外的所有結(jié)點i都要滿足:A[Panrent(i)]≥a[i]，也就是說，某個結(jié)點的值至多與其父結(jié)點一樣大。堆中的最大元素存放在根結(jié)點中。

把堆看成一棵樹，一個堆中的結(jié)點的高度就為該結(jié)點到葉結(jié)點最長簡單路徑上邊的數(shù)目。

優(yōu)先隊列是一種用來維護一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)，其中的每一個元素都有一個相關(guān)的值，稱為關(guān)鍵字(key)。一個最大優(yōu)先隊列支持以下操作:
Insert(S,x):把元素x插入集合S中。這一操作等價于S=S∪{x}。
Maximum(S):返回S中具有最大鍵字的元素。
Extract-Max(S):去掉并返回S中的具有最大鍵字的元素。
Increase-Key(S,x,k):將元素x的關(guān)鍵字值增加到k，k的值不小于x的原關(guān)鍵字。