對于堆排序會涉及一些完全二叉樹知識。對于待排序列{10, 2, 11, 8, 7}，把它看成是一顆完全二叉樹，如下圖所示。

iOS培訓(xùn),Swift培訓(xùn),蘋果開發(fā)培訓(xùn),移動開發(fā)培訓(xùn)

　　堆分為大根堆和小根堆：大根堆表示每個根節(jié)點(diǎn)均大于其子節(jié)點(diǎn)（L(i) >= L(2i) && L(i) >= L(2i + 1)），小根堆表示每個根節(jié)點(diǎn)均小于其子節(jié)點(diǎn)（L(i) <= L(2i) && L(i) <= L(2i + 1)）。（在完全二叉樹中第i個節(jié)點(diǎn)的左子節(jié)點(diǎn)為2i，其右字節(jié)點(diǎn)為2i + 1）

　　本文將以大根堆的構(gòu)建作為示例進(jìn)行講解。

　　堆排序的第一步——構(gòu)建初始堆。如何構(gòu)建初始堆呢？根據(jù)定義，關(guān)鍵點(diǎn)在于每個根節(jié)點(diǎn)。觀察上述待排序列的完全二叉樹，不難發(fā)現(xiàn)存在節(jié)點(diǎn)2和節(jié)點(diǎn)10有子節(jié)點(diǎn)，它們是需要關(guān)注的節(jié)點(diǎn)。

iOS培訓(xùn),Swift培訓(xùn),蘋果開發(fā)培訓(xùn),移動開發(fā)培訓(xùn)

　　如何定位節(jié)點(diǎn)2呢？發(fā)現(xiàn)它是葉子節(jié)點(diǎn)，或者最后一個節(jié)點(diǎn)的父節(jié)點(diǎn)，根據(jù)完全二叉樹的性質(zhì)可知