今天下午有個(gè)大型招聘會(huì)在學(xué)交逛绵，好多人怀各。倔韭。下午去做了訊飛的筆試。好多知識(shí)點(diǎn)都不清楚瓢对，不忍直視寿酌。。
堆
堆實(shí)際上是一棵完全二叉樹(shù)硕蛹，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)：
任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字幅垮。
堆排序的思想
1纤控、將數(shù)據(jù)初始化成堆，即將數(shù)據(jù)存儲(chǔ)到一個(gè)完全二叉樹(shù)中，再構(gòu)造大頂堆（升序）或小頂堆（降序）囱皿。
2氏堤、交換堆頂元素和最后一個(gè)元素响谓，得到一個(gè)新的堆债查，被交換到底部的黃色部分為有序，其余堆為無(wú)序且可能不滿足堆特性卵蛉，所以需要對(duì)其余部分進(jìn)行堆調(diào)整颁股，調(diào)整好后繼續(xù)將堆頂元素和最后一個(gè)堆低未排序元素進(jìn)行交換……
復(fù)雜度
從上述過(guò)程可知，堆排序其實(shí)也是一種選擇排序傻丝，是一種樹(shù)形選擇排序甘有。只不過(guò)直接選擇排序中，為了從R[1...n]中選擇最大記錄桑滩，需比較n-1次梧疲，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實(shí)上這n-2次比較中有很多已經(jīng)在前面的n-1次比較中已經(jīng)做過(guò)运准，而樹(shù)形選擇排序恰好利用樹(shù)形的特點(diǎn)保存了部分前面的比較結(jié)果幌氮，因此可以減少比較次數(shù)。對(duì)于n個(gè)關(guān)鍵字序列胁澳，最壞情況下每個(gè)節(jié)點(diǎn)需比較log2(n)次该互，因此其最壞情況下時(shí)間復(fù)雜度為nlogn。堆排序?yàn)椴环€(wěn)定排序韭畸，不適合記錄較少的排序
堆的存儲(chǔ)： 一般用數(shù)組來(lái)表示堆宇智，若根結(jié)點(diǎn)存在序號(hào)0處， i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i-1)/2胰丁。i結(jié)點(diǎn)的左右子結(jié)點(diǎn)下標(biāo)分別為2i+1和2i+2随橘。（注：如果根結(jié)點(diǎn)是從1開(kāi)始，則左右孩子結(jié)點(diǎn)分別是2i和2i+1锦庸。）
參考原文
http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html
http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html
