《算法导论》CLRS算法C++实现（三）P75 堆排序

第六章堆排序

主要分为三个子算法。算法MAX-HEAPIFY(A, i)为调整堆，算法BUILD-MAX-HEAP(A)为建堆，算法HEAPSORT(A)为堆排序。运行环境Code::Blocks 10.05。

MAX-HEAPIFY(A, i)

 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4     then largest ← l
 5 else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7     then largest ← r
 8 if largest ≠ i
 9     then swap(A[i], A[largest])
10     MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A)

heap-size[A] ← length[A]
for i ← ⌊length[A]/2⌋ down to 1
    do MAX-HEAPIFY(A, i)

HEAPSORT(A)

1 BUILD-MAX-HEAP(A)
2 for i ← length[A] downto 2
3     do exchange A[1] ↔ A[i]
4     heap-size[A] ← heap-size[A] - 1
5     MAX-HEAPIFY(A, 1)

C++代码实现

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 //交换x和y
 6 
 7 void swap(int* x, int* y)
 8 {
 9     int temp;
10     temp = *x;
11     *x = *y;
12     *y = temp;
13 }
14 
15 //返回左孩子的下标
16 inline int left(int i)
17 {
18     return 2 * i + 1;
19 }
20 
21 //返回右孩子的下标
22 inline int right(int i)
23 {
24     return 2 * i + 2;
25 }
26 
27 //返回父结点
28 inline int parent(int i)
29 {
30     if(i % 2)
31         return (i - 1) / 2;
32     return (i - 2) / 2;
33 }
34 
35 void maxHeapify(int* arr, int i, int heapsize)
36 {
37     int l = left(i);
38     int r = right(i);
39     int largest;
40     if((l < heapsize) && (arr[l] > arr[i]))
41         largest = l;
42     else
43         largest = i;
44     if((r < heapsize) && (arr[r] > arr[largest]))
45         largest = r;
46     if(largest != i)
47     {
48         swap(arr[i], arr[largest]);
49         maxHeapify(arr, largest, heapsize);
50     }
51 }
52 
53 void buildMaxHeap(int* arr, int length)
54 {
55     int i;
56     for(i = length / 2; i >= 0; i--)
57     {
58         maxHeapify(arr, i, length);
59     }
60 }
61 
62 void heapSort(int* arr, int length)
63 {
64     int i, heapsize = length;
65     buildMaxHeap(arr, length);
66     for(i = heapsize - 1; i > 0; i--)
67     {
68         swap(arr[0], arr[i]);
69         heapsize--;
70         maxHeapify(arr, 0, heapsize);
71     }
72 }
73 
74 int main()
75 {
76     int arr[] = {0, 2, 6, 98, 34, -5, 23, 11, 89, 100, 7};
77     heapSort(arr, 11);
78     for(int i = 0; i < 11; i++)
79     {
80         cout << arr[i] << " ";
81     }
82     cout << endl;
83     return 0;
84 }