堆排序

缘起

堆排序又叫做优先队列. 在c++ 的STL中的模板类priority_queue\以及java中的java.util.PriorityQueue 无疑都给出了堆的实现. 这个算法属于内排序中最快、性能最稳定（快排虽然也是O(nlogn)但是最坏亦可以堕落到O（n^2），而堆排稳定在O（nlogn））的一类算法, 但是因为涉及到非相邻元素之间的交换, 所以堆排不是稳定的排序。 但是堆排序是就地算法.

分析

本程序要处理的问题无非是两个，一是如何建立堆（工欲善其事必先利其器，连堆都没有，何谈用堆来排序？），二是如何用堆来进行排序,而这两件事情都涉及堆的维护操作，堆的维护操作有两个一个是siftUp(新加入一个元素，然后这个元素往上移)另一个是siftDown(将不合时宜的堆顶元素往下移)
堆的数据结构就是一棵完全二叉树，而我们知道完全二叉树可以用数组来模拟.我们给它起一个名字叫做堆数组(heapArray) 注意，从小到大排序的话要建立的是大根堆而不是小根堆，这样就能每次出堆的时候直接将当前堆中的最大数放在末尾.本程序演示建立大根堆从小到大排序.

ps： 小根堆指的是完全二叉树如果父节点的值都比子节点要小, 反之就是大根堆. 更确切地说, 小根堆指的是父节点的优先级比子节点低, 所以小根堆堆顶是优先级最低的节点, 而大根堆是指父节点优先级比子节点都要高. 所以大根堆的堆顶元素是优先级最高的节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "stdafx.h"
#include <iostream>

#pragma warning(disable:4996)

//#define LOCAL
using namespace std;

struct Heap // 大根堆结构
{
	int n; // 堆中元素的实际个数
	int *heapArray; // 堆数组, 从1开始存储数据, 0索引不用于存储数据

	void siftdown(int index) // heapArray[index] 数据往下滚, 直至符合大根堆的定义
	{
		bool isok = false; // 是否已好了
		while(!isok && index *2 <=n) // 如果还没有调整好, 并且有左孩子
		{
			int tmp = index;
			if (heapArray[index] < heapArray[2*index]) tmp = 2*index; // 则tmp变成了heapArray[index] 和 左孩子heapArray[2*index]之间的最大者的索引
			if (2*index+1 <= n && heapArray[2*index+1]>heapArray[tmp]) // 如果有右孩子 并且还比index和左孩子之间的最大者还要大, 则index应该和右孩子交换
			{
				swap(heapArray[index],heapArray[2*index+1]);
				index = 2*index+1; // index跳到右孩子
			}
			else if (tmp!=index) // 如果没有右孩子或者右孩子的值并不大于右孩子的值, 则意味着我们不需要和右孩子交换, 即使要交换, 也只是和左孩子交换, 那问题来了, 到底要不要交换index和其左孩子呢? 就看tmp有没有等于2*index
			{
				swap(heapArray[tmp], heapArray[index]);
				index = tmp; // index跳到左孩子，为下一次while做准备
			}
			else isok = true; // 说明都不需要和左孩子交换, 则index已经搞好了, 
		}
	}
	// 从这个构造函数就知道堆排是就地算法
	Heap(int *a, int n):heapArray(a),n(n){ for (int i = n/2; i; i--) siftdown(i); }  // 建堆算法 时间复杂度是O(n) 这是符合常理的, 因为求大根堆相当于求出数组最大值, 求一个数组的最大值的朴素算法的复杂度也就是O(n)，所以这是合理的. 注意, 为什么要从下往上调用siftdown? 因为这和siftdown的算法有关, siftdown使得父节点大于两个子节点，如果从上往下调用siftdown的话, 就像下面的图中, A已经siftdown调整好了, 即A节点已经找到了属于自己的位置（注意,siftdown只能保证调用的节点找到属于自己的位置, 并不能保证一路按序排列）,注意,此过程中,B节点的值可能也发生变化, 然后对B调用siftdown, 则B也找到属于自己的位置, 但是B的节点的新值可能比此时A节点的来的大哦. 但是因为siftdown只会调整到B，则A和B之间的关系就无法保证是大根堆了. 但是如果从下往上调用siftdown就不一样了. 因为后面调用siftdown的总是更高层的节点. 所以能保证堆结构.

	void heapsort() // 堆排
	{
		while(n>1) // 只要还有超过1个的元素，就还有的比
		{
			swap(heapArray[1],heapArray[n]); // 堆结构初始化完成 之后, heapArray[1]就是最大元素, 将其换到末尾, 成为最大元素
			n--;
			siftdown(1); // 则heapArray[1]变成了原先的heapArray[n], 但是heapArray[n]显然未必是最大的. 所以要siftdown. 但是因为heapArray[n]已经归位（最大元素），所以n要--, 不然刚换到最末位元素的最大元又要顶上去

		}
	}
};

int kth(int *a, int k, int n) // 求a数组从小到大排名第k的元素, 其中a是长度为n的数组 其中a[1,..,n] 用于存储数据
{
	Heap heap(a, k) ; // 使用a[1,...,k]维护一个k大小的大根堆
	for (int i = k+1; i<=n; i++)
	{
		if (a[i] >= heap.heapArray[1]) continue; // 因为 heap.heapArray[1] 至少是排k的, 所以a[i]排名不会<k
		heap.heapArray[1] = a[i];
		heap.siftdown(1); // 重新调整（时间复杂度是O(logn)）
	}
	return heap.heapArray[1]; // 最后顶上的就是从小到大排行第k的
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	// 含有14个元素的数组
	int a[15]={0,99,5,36,7,22,17,46,12,2,19,25,28,1,92};//a的0索引不用于存储数据
	Heap heap(a, 14);
	heap.heapsort();
	puts("排序后");
	for (int i=  1; i<=14; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n第3大的元素是%d\n", kth(a, 8, 14));
	return 0;
}

ps: 这个堆排序和优先队列有什么关系呢? 相信你如果把上述算法弄清楚了的话, 就知道堆排序的核心——堆数组可以帮我们这个忙. 因为比较大小的话, 我们完全可以根据特定的价值观设计我们自己的比较器. 从而实现某种优先队列. 举个例子 , prim算法或者dijkstra算法每个for循环的时候要从尚未加入到MST中的顶点中到达MST距离最短的点. 这个过程就是选择最小, 则只需要构造小根堆（优先队列）.则就可以将这两个图算法的复杂度降低为nlogn而不是原先的 n^2.

最后说一句, 搞清楚实现堆的原理即可, 竞赛的时候或者真正写算法的时候, 还是用现成的库的.