算法導論 第6章 堆排序

相比歸并排序和插入排序，堆排序 的時間複雜度是O(nlgn)與歸并排序相同，且具有與插入排序一樣的空間原址性，即任何時候隻需要常數個額外的元素空間存儲臨時資料。是以堆排序是一種集合了這兩種算法優點的排序算法。

堆排序引入了稱為 堆 的資料結構，堆是一個數組，可以看成一個近似的完全二叉樹，樹上每個節點對應一個數組元素。

另樹的根節點為A[1]，且給定一個節點的下标i，他的父節點下标為i/2向下取整，左孩子為2i，右孩子為2i+1。

最大堆 是指除了根節點以外所有節點滿足父節點的值大于等于目前節點的值的堆。最小堆 是指除了根節點以外所有節點滿足父節點的值小于等于目前節點的值的堆。如一個最大堆：

堆排序使用最大堆，最小堆通常用于建構優先隊列。

維護堆

MAX-HEAPIFY定義了維護最大堆性質的過程，輸入為數組A和下标i。該過程假定節點的左右子樹都是最大堆，通過逐級下降地比較目前節點和子節點來調整至整個樹為最大堆：

該過程時間複雜度O(lgn)。

對i=2的子樹執行過程：

建立堆

BUILD-MAX-HEAP定義了建立堆的過程，其中對所有非葉子節點從下到上依次調用MAX-HEAPIFY，都執行完後即可得到最大堆：

該過程時間複雜度O(n)。

對數組{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}的執行過程：

堆排序

HEAPSORT實作了建立最大堆并輸出排序結果的過程，該過程每次将根節點調換至最後位置，并重新調整堆至最大堆：

該過程時間複雜度O(nlgn)。

執行過程：

優先隊列

堆的另一個應用是作為高效的 優先隊列，用于計算機系統的作業排程等場合。優先隊列是一種用來維護一組元素的資料結構，其中每個元素有一個關鍵字。優先隊列支援插入、傳回最大（小）關鍵字、去掉并傳回最大（小）關鍵字、将元素的關鍵字值增大（減小）等操作。