1.1　堆

本節(jié)介紹一種常見的數(shù)據(jù)結構—二叉堆（簡稱堆），通過圖文講解和代碼實現(xiàn)來了解這個重要的數(shù)據(jù)結構。

1.1.1　堆的定義

堆（Heap）是一棵完全二叉樹。其最重要的性質(zhì)就是“兒子”的值一定不小于（或大于）“父親”的值（分別稱為小頂堆和大頂堆，下文使用大頂堆）。應用場景包括堆排序和優(yōu)先隊列等。用數(shù)組存堆時，對于任意一個節(jié)點x，其左、右子節(jié)點的標號分別為2x+1和2x+2。

堆的邏輯結構和存儲結構如圖1.1所示。

1.1.2　建堆

建堆的核心內(nèi)容是調(diào)整堆，使二叉樹滿足堆的定義（每個節(jié)點的值都不大于其父節(jié)點的值）。調(diào)堆的過程應該從最后一個非葉子節(jié)點開始，一直調(diào)整到根節(jié)點。

堆排序過程示例如圖1.2所示。

1.1.3　堆排序算法

設堆有n個元素，每一次調(diào)整堆，堆頂位置將得到堆的最大值，然后將堆頂元素和最后一個元素互換，對前n-1個元素繼續(xù)調(diào)整，直到整個堆有序為止。堆排序時間復雜度為O（log2N）。堆排序是不穩(wěn)定排序。

代碼實現(xiàn)如下所述。