算法思想
堆排序利用了最大堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最?。┻@一特征，使得在當(dāng)前無序區(qū)中選取最大（或最?。╆P(guān)鍵字的記錄變得簡單。
1.用最大堆排序的基本思想
（1）先將初始文件R[1..n]建成一個(gè)最大堆，此堆為初始的無序區(qū)
（2）再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
（3）由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。
……
直到無序區(qū)只有一個(gè)元素為止。
2.最大堆排序算法的基本操作：
（1）建堆，建堆是不斷調(diào)整堆的過程，從len/2處開始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)，此處len是堆中元素的個(gè)數(shù)。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度，len/2表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過程，結(jié)果是線性的O(n)。
（2）調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會(huì)用到，而且在堆排序過程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪?jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程，這是一個(gè)遞歸的過程。調(diào)整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。
（3）堆排序：堆排序是利用上面的兩個(gè)過程來進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。堆排序過程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)（調(diào)用一次）；調(diào)整堆的時(shí)間復(fù)雜度是lgn，調(diào)用了n-1次，所以堆排序的時(shí)間復(fù)雜度是O(nlgn)[2]
注意
（1）只需做n-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。
（2）用小根堆排序與利用最大堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止

Swift示例
（1）基于最大堆實(shí)現(xiàn)升序排序

func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i {  adjustMaxHeap(&a, len: a.count, parentNodeIndex: i) }} func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0，說明已經(jīng)無序區(qū)已經(jīng)縮小到0 guard len > 1 else {  return }  // 父結(jié)點(diǎn)的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1  // 如果連左孩子都沒有， 一定沒有右孩子，說明已經(jīng)不用再往下了 guard leftChildIndex < len else {  return }  let rightChildIndex = 2 * parentNodeIndex + 2  // 用于記錄需要與父結(jié)點(diǎn)交換的孩子的索引 var targetIndex = -1  // 若沒有右孩子，但有左孩子，只能選擇左孩子 if rightChildIndex > len {  targetIndex = leftChildIndex } else {  // 左、右孩子都有，則需要找出最大的一個(gè)  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex }  // 只有孩子比父結(jié)點(diǎn)還要大，再需要交換 if a[targetIndex] > a[parentNodeIndex] {  let temp = a[targetIndex]    a[targetIndex] = a[parentNodeIndex]  a[parentNodeIndex] = temp    // 由于交換后，可能會(huì)破壞掉新的子樹堆的性質(zhì)，因此需要調(diào)整以a[targetIndex]為父結(jié)點(diǎn)的子樹，使之滿足堆的性質(zhì)  adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex) }} func maxHeapSort(inout a: [Int]) { guard a.count > 1 else {  return }  initHeap(&a)  for var i = a.count - 1; i > 0; --i {  // 每一趟都將堆頂交換到指定范圍內(nèi)的最后一個(gè)位置  if a[0] > a[i] {   let temp = a[0]      a[0] = a[i]   a[i] = temp  }  print(a)  print(i - 1)  // 有序區(qū)長度+1，而無序區(qū)長度-1，繼續(xù)縮小無序區(qū)，所以i-1  // 堆頂永遠(yuǎn)是在0號(hào)位置，所以父結(jié)點(diǎn)調(diào)整從堆頂開始就可以了  adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0)  print(a) }}