现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看做是一种数据结构。
(二叉)堆的定义:
1)它是一个数组,可以被看成是一棵近似的完全二叉树,树上的每一个节点看做是数组中的每一个元素。
2)堆分为最大堆和最小堆,最大堆中每一棵子树的父节点的值大于孩子节点,最小堆则相反。
3)表示堆的数组A包括两个属性:A.length和A.heap_size。前者是数组元素的个数,后者是堆元素的个数,heap_size <= length。(怎么理解这里,想象一棵树的节点在减少,但其表示的数组的个数还是不变的)。
4)二叉堆是最常用的,除此之外,还有多叉堆,如习题6-2的d-叉堆。
5)已知一个节点的坐标,容易得到其父节点和孩子节点的坐标:PARENT(i) = i/2; LEFT(i) = 2*i; RIGHT(i)=2*i+1。
由于二叉堆可以看做是一棵完全二叉树,所以树的一些定理,结论可以应用到堆上,如高度为h的堆中元素个数最多为:2^h,最少为:2^(h+1) - 1; 含n个元素的堆高度为:lgn。
堆排序:
为了实现堆排序,需要有这样的几个过程:
1)Build_Max_Heap():建立最大堆,将无序的输入数组构造出一个最大堆;
2)Max_Heapify():维护一个最大堆,即保证满足最大堆的性质;
3)Heap_Sort():堆排序。
以上函数的思路也是比较简单,在此就不做过多记录,即便记录,也是照着书本上的流程来一遍。
首先,Max_Heapify()是一个很关键的函数,它要保证堆中元素在以后的操作过程中,不管怎么变,都要保证满足最大堆的性质,即父节点的值永远大于孩子节点,知道了这一点,就不难写出代码:
函数原型:Max_Heapify( int A[], /* int heap_size, */ int index )
1 void MaxHeapify_Recur(int arr[], int heap_size, int index)
2 {
3 if (index <=0 && index >= heap_size)
4 return;
5
6 int left = LEFT(index);
7 int right = RIGHT(index);
8 int largest;
9
10 if (left < heap_size && arr[left] > arr[index])
11 largest = left;
12 else
13 largest = index;
14
15 if (right < heap_size && arr[right] > arr[largest])
16 largest = right;
17
18 if (largest != index) {
19 Swap(arr[index], arr[largest]);
20 MaxHeapify_Recur(arr, heap_size, largest);
21 }
22 }
上面实现的是一个递归的版本,也是书本上的版本,同时习题6.2-5要求实现非递归的版本,其实改动很小,只需加入一个标识符即可,实现如下:
1 void MaxHeapify(int arr[], int heap_size, int index)
2 {
3 if (index < 0 && index >= heap_size)
4 return;
5
6 bool isHeapify = true; //标识最大堆是否处理完
7 while (isHeapify && index < heap_size) {
8 int left = LEFT(index);
9 int right = RIGHT(index);
10 int largest;
11
12 if (left < heap_size && arr[left] > arr[index])
13 largest = left;
14 else
15 largest = index;
16
17 if (right < heap_size && arr[right] > arr[largest])
18 largest = right;
19
20 if (largest != index) {
21 Swap(arr[index], arr[largest]);
22 index = largest;
23 }
24 else
25 isHeapify = false;
26 }
27 }
其次,Build_Max_Heap()的实现需要知道下面一条定理( 习题6.1-7 ) :
当用数组表示存储n个元素的堆时,叶节点下标分别是n/2+1, n/2+2, ..., n (结合树高度的性质,很好证明).
知道了这个定理,为了建立最大堆,我们就可以从第一个非叶子节点开始往后遍历,直到根节点,调用Max_Heapify()来得到一个最大堆,实现如下:
函数原型:Build_Max_Heap( int A[], /* int heap_size, */ )
1 void BuildMaxHeap(int arr[], int heap_size)
2 {
3 if (heap_size == 0)
4 return;
5
6 for (int i = (heap_size-1)/2; i >= 0; i--)
7 MaxHeapify(arr, heap_size, i);
8 }
至此,排序思路也就出来了:先建立最大堆,得到最大元素,然后将最大元素放在数组末尾,然后调用Max_Heapify()维护最大堆,依次下去,就得到排序的数组,实现如下:
函数原型:Heap_Sort( int A[], /* int heap_size, */ )
1 void HeapSort(int arr[], int length)
2 {
3 if (length == 0)
4 return;
5
6 int heap_size = length;
7 BuildMaxHeap(arr, heap_size);
8 for (int i = length-1; i >= 1; i --) {
9 Swap(arr[0], arr[i]);
10 heap_size --;
11 MaxHeapify(arr, heap_size, 0);
12 }
13 }
堆排序的时间复杂度:
Max_Heapify()可以看到是在不断遍历树,最坏情况下是从根节点开始,则n个节点的树高为lgn,所以其时间复杂度为O(lgn)。
Build_Max_Heap()经过严格推导,可得时间复杂度为线性的,为O(n)。
所以,Heap_Sort()就为O(nlgn)。
同样的思路可以实现最小堆,下面贴出最大堆完整实现的代码:
1 #include <iostream>
2
3 using namespace std;
4
5
6 //#include "HeapSort.h"
7
8 #define PARENT(x) ((x-1)/2) //求 x 父节点的下标
9 #define LEFT(x) ((x)*2+1) //求 x 左孩子的下标
10 #define RIGHT(x) ((x)*2+2) //求 x 右孩子的下标
11
12 void MaxHeapify(int arr[], int heap_size, int index); //维护最大堆的性质
13 void MaxHeapify_Recur(int arr[], int heap_size, int index); //递归
14 void BuildMaxHeap(int arr[], int heap_size); //从一个无序的数组中构造一个最大堆
15 void HeapSort(int arr[], int length); //堆排序
16 void Swap(int &a, int &b);
17
18 void MaxHeapify(int arr[], int heap_size, int index)
19 {
20 if (index < 0 && index >= heap_size)
21 return;
22
23 bool isHeapify = true; //标识最大堆是否处理完
24 while (isHeapify && index < heap_size) {
25 int left = LEFT(index);
26 int right = RIGHT(index);
27 int largest;
28
29 if (left < heap_size && arr[left] > arr[index])
30 largest = left;
31 else
32 largest = index;
33
34 if (right < heap_size && arr[right] > arr[largest])
35 largest = right;
36
37 if (largest != index) {
38 Swap(arr[index], arr[largest]);
39 index = largest;
40 }
41 else
42 isHeapify = false;
43 }
44 }
45
46 void MaxHeapify_Recur(int arr[], int heap_size, int index)
47 {
48 if (index <=0 && index >= heap_size)
49 return;
50
51 int left = LEFT(index);
52 int right = RIGHT(index);
53 int largest;
54
55 if (left < heap_size && arr[left] > arr[index])
56 largest = left;
57 else
58 largest = index;
59
60 if (right < heap_size && arr[right] > arr[largest])
61 largest = right;
62
63 if (largest != index) {
64 Swap(arr[index], arr[largest]);
65 MaxHeapify_Recur(arr, heap_size, largest);
66 }
67 }
68
69 void BuildMaxHeap(int arr[], int heap_size)
70 {
71 if (heap_size == 0)
72 return;
73
74 for (int i = (heap_size-1)/2; i >= 0; i--)
75 MaxHeapify(arr, heap_size, i);
76 }
77
78 void HeapSort(int arr[], int length)
79 {
80 if (length == 0)
81 return;
82
83 int heap_size = length;
84 BuildMaxHeap(arr, heap_size);
85 for (int i = length-1; i >= 1; i --) {
86 Swap(arr[0], arr[i]);
87 heap_size --;
88 MaxHeapify(arr, heap_size, 0);
89 }
90 }
91
92 void Swap(int &a, int &b)
93 {
94 int temp = a;
95 a = b;
96 b = temp;
97 }
98
99 // int main()
100 // {
101 // int arr[10] = {10,14,16,8,7,9,3,2,4,1};
102 // HeapSort(arr, 10);
103 // for (int i = 0; i < 10; i ++)
104 // cout << arr[i] << " ";
105 // return 0;
106 // }