做过系统编程的人都知道，几乎任何系统都会提供一种时钟机制，也就是SetTimer调用，你给系统提供一个回调函数，顺带一个超时时间，一旦时间过去后，系统就会回调你提供的函数。问题是，你如何实现一个系统的Timer机制。
实现Timer机制的办法是使用堆排序。所谓的'堆'是一种特殊的二叉树,它跟内存管理上的'堆'没有任何联系。数据结构'堆'，实际上是把一个数组中的元素按照某种次序组合成一颗二叉树，二叉树根节点的特性决定了堆的特性，如果二叉树根节点的值是数组元素中的最大值，那么这颗二叉树表示的堆叫大堆，如果二叉树根节点的值是元素中的最小值，那么二叉树表示的堆叫小堆。
例如给定一个数组：
heapArray: 16, 14, 10, 8, 7 , 9 , 3, 2, 4 , 1
把他们构建成一个大堆，结果如下：
节点旁边的数字代表它在数组中的下标，我们可以看到，给定一个节点下标i,那么它在对中对应的父节点就是i/2, 必然下标为2和3的节点，其父节点是16，而16的下标恰好是1.
给定一个节点下标为i,那么它在堆中的左孩子对应在数组中的下标为2*i,右孩子对应的下标为2*i+1,于是我们有如下三种操作：
int parent(int i) {
return i/2;
}
int left(int i ) {
return 2*i;
}
int right(int i) {
return 2*i+1;
}
堆虽然是二叉树，但不是排序二叉树，所以无需要求做子树节点一定小于父节点，父节点一定小于右子树节点。但它必须维持一个特性，那就是如果堆是大堆，那么必须保证父节点大于孩子节点；如果是小堆，那么必须保证父节点小于孩子节点。于是如果二叉树是大堆，那么根节点肯定是所以元素中的最大那个，如果是小堆，那么根节点肯定是所有元素中值最小的那个。
由于堆是一颗二叉树，所以堆有高度之分，一个含有n个元素的数组转换为堆时，堆的高度就是lg(n). 接下来我们看看，如果大堆中，某个节点的值变得比它孩子的值还要小，那么我们应该如何调整才能使得前面所说的大堆性质保持不变，我们假定当前的大堆元素个数用heapSize来表示。假如下标为i的元素它的数值被改变了，我们可以通过下面代码调整大堆，从而使得堆的性质保持不变：
private void maxHeapify(int i) {
//这里+1的原因是，数组下标是从0开始，而算法对数组下标是从1开始
i++;
int l = left(i);
int r = right(i);
//减1的原因是，数组元素的下标是由0起始的，而算法对数组下标的起始是由1开始
i--;
l--;
r--;
int largest = -1;
if (l < heapSize && heapArray[l] > heapArray[i]) {
largest = l;
} else {
largest = i;
}
if (r < heapSize && heapArray[r] > heapArray[largest]) {
largest = r;
}
if (largest != i) {
int temp = heapArray[i];
heapArray[i] = heapArray[largest];
heapArray[largest] = temp;
maxHeapify(largest);
}
}
它的思路很简单，如果某个节点值变小了，那么它就找到他左右孩子节点中值最大的那个，然后两种互换，这个动作一直进行，直到走到堆的底部为止。注意，上面代码的逻辑假设节点i的左子树和右子树都满足大堆的性质。假设一个满足条件的二叉树如下：
节点4比它的左右孩子要小，但以节点14和7为根的二叉树是满足大堆性质的，由此我们可以根据上面代码逻辑进行调整。先从节点4的左右孩子中找到最大的一个，显然左孩子是14是最大的，于是把4和14交换：
节点4下降一层，然后再和他的左右节点中值最大的那个互换，从上图看，节点4应该和节点8互换，交换后结果如下：
我们看到，这一次调换后，整个二叉树满足大堆的性质。在调整过程中，每调整一次，原来元素就下降一层，由于堆的高度是lg(n),所以上面调整代码的时间复杂度是O(lg(n))。
接下来，我们可以使用maxHeapify来将一个数组构建成一个大堆，前面我们说如果一个元素在数组中的下标是i,那么它的左孩子下标为2*i,右孩子下标为2*i+1,这样一来，所有处于数组后半部分的元素只能处于大堆最底部，也就是只能做叶子。这里要注意的是，任何单个节点本身就是一个大堆。我们使用下面的算法来把一个数组构建成大堆：
private int[] buildMaxHeap() {
for (int i = heapSize / 2; i >= 0; i--) {
maxHeapify(i);
}
return heapArray;
}
代码里的循环是从数组的中点开始的，前面我们提到过，中部后面的元素都是叶子节点，叶子节点自己就满足大堆属性。在前面我们也演示过，maxHeapify这个调用能够保证每个以每个节点为根的二叉树满足大堆属性，于是循环结束后的数组就变成了一个满足大堆性质的二叉树。举个例子，假设有数组
A:1，5，3，4，2
数组长度是5，上面代码则从下标为2处，也就是元素3开始循环，3的左孩子是下标为4的元素2,由此3和2两个节点构成了一个大堆，接着循环往前走到元素5，5的左孩子是3，右孩子是4，此时节点5和它的两个孩子满足大堆性质，循环继续往前走，来到元素1，它的左孩子是节点5，右孩子是3，此时maxHeapify调用将对元素进行调整，它先把节点1和节点5对换，然后再把节点1和节点4对换，最后数组A的情况如下：
A: 5, 4, 3, 1, 2
数组元素的排列是满足大堆属性的。
综合起来，我们得到构建一个大堆的代码如下：
public class HeapSort {
private int heapSize = 0;
private int[] heapArray = null;
public HeapSort(int[] arr) {
heapSize = arr.length;
heapArray = arr;
}
private int parent(int i) {
return i/2;
}
private int left(int i) {
return i*2;
}
private int right(int i) {
return i*2+1;
}
private void maxHeapify(int i) {
//这里+1的原因是，数组下标是从0开始，而算法对数组下标是从1开始
i++;
int l = left(i);
int r = right(i);
//减1的原因是，数组元素的下标是由0起始的，而算法对数组下标的起始是由1开始
i--;
l--;
r--;
int largest = -1;
if (l < heapSize && heapArray[l] > heapArray[i]) {
largest = l;
} else {
largest = i;
}
if (r < heapSize && heapArray[r] > heapArray[largest]) {
largest = r;
}
if (largest != i) {
int temp = heapArray[i];
heapArray[i] = heapArray[largest];
heapArray[largest] = temp;
maxHeapify(largest);
}
}
public int[] buildMaxHeap() {
for (int i = heapSize / 2; i >= 0; i--) {
maxHeapify(i);
}
return heapArray;
}
}
利用上面代码，对给定任意数组构建一个大堆：
public class Heap {
public static void main(String[] s) {
int A[] = new int[]{1,2 ,3,4,7,8,9,10,14,16};
HeapSort hs = new HeapSort(A);
int[] heap = hs.buildMaxHeap();
for (int i = 0; i < heap.length; i++) {
System.out.print(heap[i] + " ");
}
}
}
上面代码运行后，输出的数组结果为：
16 14 9 10 7 8 3 1 4 2
上面数组对应的大堆二叉树为：
maxHeapify其时间复杂度为lg(n),所以buildMaxHeap的时间复杂度为n*lg(n).
大堆的特点是，所有元素的最大值在根节点，对应的也就是最大值会放置到数组的头部，我们可以利用这个特性来对数组进行排序，这种排序法叫堆排序。对含有n个元素的数组，我们构建一个大堆，那么最大值肯定在堆的根节点，对应于数组就是最大值会在数组下标为0处，然后我们把第0个元素和最后一个元素互换，这样最大值就排在了数组的n-1处。接着对数组的前n-1个元素进行相同的步骤，这样第二大的元素就会排在数组的n-2处，就这样反复进行，整个数组就能实现从小到大排序了，对应代码如下：
public void heapSort() {
buildMaxHeap();
for (int i = heapArray.length - 1; i > 0; i--) {
//值最大的元素在根节点对应到数组就是值最大的元素在数组的起始位置
int temp = heapArray[i];
heapArray[i] = heapArray[0];
heapArray[0] = temp;
heapSize--;
maxHeapify(0);
}
}
上面代码上运行后，再把元素的内容打印出来：
hs.heapSort();
System.out.println("\nArray after heap sort is :");
for (int i = 0; i < heap.length; i++) {
System.out.print(A[i] + " ");
}
打印后结果如下：
1 2 3 4 7 8 9 10 14 16
由此可见，数组中的元素已经被排好序了。heapSort执行时，调用了buildMaxHeap(),其时间复杂度我们前面分析过是n*lg(n),其中的for循环次数是n,每次循环调用了maxHeapify(),其复杂度是lg(n)，所以for循环所需要的时间复杂度是n*lg(n),由此一来heapSort的时间复杂度，也就是堆排序的时间复杂度是O(n*lg(n))。
使用堆排序实现优先级队列
最大优先级队列是这样一种数据结构，它是一组元素的集合，同时它支持以下三种操作：
1, insert(x), 把一个元素加入集合。
2, maximun(), 返回整个集合中的最大值
3, extractMax(), 把集合中的最大值取出来并从集合中去除。
4, increaseKey(i ,k), 把集合中的第i个元素的值增加为k。
假设我们有一系列任务，任务的优先级不同，优先级越大任务越重要，这样的话我们就可以把任务使用最大优先级队列进行调度。与最大优先级队列等价的是最小优先级队列，它的原理跟最大优先级队列一样，只不过把返回最大值改为最小值，把元素的值增加k变为减少k,系统的Timer机制就是使用最小优先级队列实现的。
我们看看上面的几种操作如何基于最大堆实现，首先Maximun()实现简单，我们只要把数组构建成大堆后，返回数组的首个元素即可。于是有
public int maximun() {
return heapArray[0];
}
Extract_Maximun()需要把最大值拿掉后，剩下的元素任然能满足相应操作，假设我们数组中元素最大是16，第二大是14，那么调用一次Extract_Maximun()后返回16，然后调用maximun()时要返回14，它的做法是把返回堆的根元素，把数组最后一个元素跟根元素互换，接着把堆的大小由原来的n变为n-1,然后调用maxHeapify对前n-1个元素调整成大堆。代码如下：
int extractMax() {
if (heapSize < 1) {
return -1;
}
int max = heapArray[0];
heapArray[0] = heapArray[heapSize - 1];
heapSize--;
maxHeapify(0);
return max;
}
extractMax内部调用了maxHeapify(),由于后者的时间复杂度是O(lgn),所以extractMax()的时间复杂度是O(lg(n)).
完成上面代码后，通过以下代码进行调试运行：
System.out.println("\nmaximun is : " + hs.maximun());
hs.extractMax();
System.out.println("the maximun after extractMax is : " + hs.maximun());
程序输出结果为：
maximun is : 16
the maximun after extractMax is : 14
我们把最大值16从堆中抽出后，再次调用maximun()得到结果为第二大的节点14，由此可见我们代码实现的逻辑是正确的。
我们再看看increaseKey的实现：
public void increaseKey(int i, int k) {
if (heapArray[i] > k) {
return;
}
heapArray[i] = k;
while (i > 0 && heapArray[parent(i)] < heapArray[i]) {
int temp = heapArray[parent(i)];
heapArray[parent(i)] = heapArray[i];
heapArray[i] = temp;
i = parent(i);
}
}
当某个节点值变大后，为了保证大堆性质不变，如果它的值比父节点大，那么把它和父节点互换，这个流程一直执行到根节点，这样就可以保持整个大堆的性质不变了，该操作的时间复杂度是O(lg(n))。完成代码后，我们在入口处添加如下代码来检验效果：
hs.increaseKey(9, 17);
System.out.println("\nThe maximun after increaseKey is : " + hs.maximun());
数组第9个元素，也就是最后一个元素的值是2，我们通过increaseKey调用把它增加到17，此时它变成了整个大堆里的最大值，再次调用maximun()得到的结果应该是17，上面代码运行后结果如下：
The maxmimun after increaseKey is : 17
由此可见，程序的实现是正确的。我们再看最后一个insert操作,给当前大堆插入一个元素并且保持堆的性质不变：
public int[] insert(int val) {
int[] mem = new int[heapArray.length + 1];
for (int i = 0; i < heapArray.length; i++) {
mem[i] = heapArray[i];
}
heapArray = mem;
heapArray[heapArray.length - 1] = Integer.MIN_VALUE;
heapSize++;
increaseKey(heapSize - 1, val);
return heapArray;
}
由于要插入一个元素，插入后堆的元素要比原来多1，因此代码先分配一个比原来大堆对应的数组多一个元素的内存，然后把原数组内容拷贝过去，接着把最后一个元素的值设置为最小值，最后使用increaseKey调用把最后的元素值增加到要插入的元素值，这样我们就能保证插入的元素可以添加到大堆的适当位置，适当堆的性质不会遭到破坏，该操作的时间复杂度与increaseKey一样，都是O(lg(n))。
我们在程序入口处使用如下代码测试上面实现的正确性：
hs.insert(20);
System.out.println("Maximun after insert is: " + hs.maximun());
我们往堆中插入一个值为20的新元素，插入后这个值将最为堆的最大值从maximun调用中返回，上面代码运行后结果如下：
Maximun after insert is: 20
由此可见，我们代码的实现在逻辑上是正确的。
到此，堆的数据结构及其相关算法原理和实现我们就介绍完了，要实现系统的Timer机制，我们只要实现一个小堆，然后在此基础上实现最小优先级队列即可。
更详细的讲解和调试演示，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
