算法导论---第6章---堆排序

1、堆排序简介

　　堆排序（heapsort）。与归并排序一样，但不同于插入排序的是，堆排序的时间复杂度是O(nlgn)。而与插入排序相同，但不同于归并排序的是，堆排序同样具有空间原址性：任何时候都只需要常数个额外的元素存储临时数据。因此，堆排序是集合了插入排序和归并排序这两种排序算法优点的一种排序算法。

2、基本过程

　　MAX-HEAPIFY过程：其时间复杂度为O(lgn)，它是维护最大堆性质的关键。

　　BUILD-MAX-HEAP过程：具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆。

　　HEAPSORT过程：其时间复杂度为O(nlgn)，功能是对一个数组进行原址排序。

3、算法描述

　　首先，堆排序算法利用BUILD-MAX-HEAP将输入数组A[1...n]建成最大堆，其中n=A.length。因为数组中的最大元素总在根节点A[1]中，通过把它与A[n]进行互换，我们可以让该元素放到正确的位置。这时候，如果我们从堆中去掉节点n（这一操作可以通过减少A.heap-size的值来实现），剩余的节点中，原来根的孩子节点仍然是最大堆，而新的根节点可能会违背最大堆的性质。为了维护最大堆的性质，我们要做的是调用MAX-HEAPIFY(A, 1)，从而在A[1...n-1]上构造一个新的最大堆。堆排序算法会不断重复这一过程，知道堆得大小从n-1降到2.

　　算法伪代码描述如下：

　　PARENT(i)

　　1　　return ⌊i/2⌋

　　LEFT(i)

　　1　　return 2i

　　RIGHT(i)

　　1　　return 2i+1

　　MAX-HEAPIFY(A, i)

　　1　　l = LEFT(i)

　　2　　r = RIGHT(i)

　　3　　if l ≤ A.heap-size and A[l] > A[i]

　　4　　　　largest = l

　　5　　else largest = i

　　6　　if r ≤ A.heap-size and A[r] > A[largest]

　　7　　　　largest = r

　　8　　if largest ≠ i

　　9　　　　exchange A[i] with A[largest]

　　10　　　 MAX-HEAPIFY(A, largest)

　　BUILD-MAX-HEAP(A)

　　1　　A.heap-size = A.length

　　2　　for i = ⌊A.length/2⌋ downto 1

　　3　　　　MAX-HEAPIFY(A, i)

　　HEAPSORT(A)

　　1　　BUILD-MAX-HEAP(A)

　　2　　for i = A.length downto 2

　　3　　　　exchange A[1] with A[i]

　　4　　　　A.heap-size = A.heap-size - 1

　　5　　　　MAX-HEAPIFY(A, 1)

4、算法代码（C++实现）

　　ps：因为伪码中数组A的起始小标为1，而实际编写C++代码中，数组的起始下标为0，所以这里要注意计算父节点、子节点的下标公式与伪码中不同，同时需要注意循环体的结束条件也与伪码中略有差异。

  1 #include <iostream>
  2 #include <math.h>
  3 #include <stdio.h>
  4 
  5 using namespace std;
  6 
  7 inline int PARENT(int i) {return (i+1)/2 - 1;};
  8 inline int LEFT(int i) {return 2*i+1;};
  9 inline int RIGHT(int i) {return (2*i+2);};
 10 
 11 void Max_Heapify(int *a, int length, int i);
 12 void Max_BuildHeap(int *a, int length);
 13 void Max_HeapSort(int *a, int length);
 14 
 15 int main()
 16 {
 17     int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
 18     int length = 10;
 19 
 20     Max_HeapSort(a, length);
 21 
 22     cout << "Result of Max_HeapSort(): " << endl;
 23     for (int i = 0; i < length; i++)
 24     {
 25         cout << a[i] << " ";
 26     }
 27     cout << endl;
 28 
 29     return 0;
 30 }
 31 
 32 
 33 void exchange(int &a, int &b)
 34 {
 35     // 交换变量 a 和 b 的值
 36     if (a == b)
 37     {
 38         return;
 39     }
 40     int tmp = a;
 41     a = b;
 42     b = tmp;
 43 }
 44 
 45 void Max_Heapify(int a[],int length, int i)
 46 {
 47     // 对数组 a 的第 i 个元素进行堆化操作
 48     if (a == NULL)
 49     {
 50         cerr << "Max_Heapify(): Array is NULL!" << endl;
 51         return;
 52     }
 53     int heap_size = length;
 54 
 55     int l = LEFT(i);
 56     int r = RIGHT(i);
 57     int largest;
 58 
 59     if (l < heap_size && a[l] > a[i])
 60     {
 61         largest = l;
 62     }
 63     else
 64     {
 65         largest = i;
 66     }
 67     if (r < heap_size && a[r] > a[largest])
 68     {
 69         largest = r;
 70     }
 71     if(largest != i)
 72     {
 73         exchange(a[i], a[largest]);
 74         Max_Heapify(a, length, largest);
 75     }
 76 }
 77 
 78 void Max_BuildHeap(int a[], int length)
 79 {
 80     // 建立最大堆
 81     if (a == NULL)
 82     {
 83         cerr << "Max_BuildHeap(): Array is NULL!" << endl;
 84         return;
 85     }
 86     for (int i = floor((length-1)/2); i >= 0; i--)
 87     {
 88         Max_Heapify(a, length, i);
 89     }
 90 }
 91 
 92 void Max_HeapSort(int a[], int length)
 93 {
 94     // 最大堆排序
 95     if (a == NULL)
 96     {
 97         cerr << "Max_HeapSort(): Array is NULL!" << endl;
 98         return;
 99     }
100     int heap_size = length;
101     Max_BuildHeap(a, length);
102 
103     cout << "Result of Max_BuildHeap(): " << endl;
104     for (int i = 0; i < length; i++)
105     {
106         cout << a[i] << " ";
107     }
108     cout << endl;
109 
110     for (int i = length-1; i >= 1; i--)
111     {
112         exchange(a[0], a[i]);
113         heap_size -= 1;
114         Max_Heapify(a, heap_size, 0);
115     }
116 }

　　运行结果如下：