堆的基本性质与排序算法的实现

前段时间申了腾讯移动开发暑期实习，昨天一轮面试被问到堆的问题（面试官人很好~）。这里的堆是数据结构中的堆，而不是操作系统的堆。然而，堆排序时间太久了，忘掉了一些基本概念，于是面试不出意外是挂掉了（当然不止堆没答上来）。这里总结一下堆的性质，为以后申公司做好准备吧！

腾讯面试官问了我一个问题，说100个数字存放在堆中，最差时间找到这个数字是多少。我不确定，先是回答了一个O(nlgn)，后来他要具体的数字，我突然断电了，想成了二叉搜索树，于是回答了“7”。。。。。于是就很尴尬了T_T

---

我们先看看什么是数据结构中的堆：

（二叉）堆是一个二叉树，可以由数组构成，也可以由链表构成。它可以被看成一棵近似的完全二叉树，树上的每一个节点对应数组或链表中的每一个元素。

（借图说话，侵删）

 

由于堆可以近似成一棵完全二叉树，所以完全二叉树有的性质（父节点与孩子节点的位置关系）堆是共享的。

//给定节点i，以下为其家族节点位置
Parent(i){
    return i/2;
}

Left(i){
    return 2i;
}

Right(i){
    return 2i+1;
}

一般来说，二叉堆分为最大堆和最小堆，又称大顶堆和小顶堆，我认为后者更形象。意思就是堆顶（树根）的数是最大的或者最小的，由此来得到一组数据中的最大值和最小值。上图就是小顶堆。 

当然，除此之外，对于大顶堆来说，所有父节点的值要大于其子节点的值；对于小顶堆来说，所有父节点的值要小于其子节点的值。而他们的兄弟节点之间并无任何大小上的关联。

而我面试犯得错误，就是认为堆节点的左孩子小于父亲，右孩子大于父亲，因此导致错误！其实也是紧张了，不然多想一想就知道我的回答有问题。

---

基本内容说完了，我们再说一说其他内容 。堆排序在排序算法中时间复杂度很小，且属于原址排序，因此我们可以通过堆来对一组数据求最值。

堆绝大部分的开销花费在了维护上。以下我们以大顶堆为例讲解其是如何维护的。

//伪代码实现
Max_Heapify(A,i){
    l = Left(i)
    r = Right(i)
    if l <= A.size() && A[l] > A[i] {
        largest = l
    }
    else {
        largest = i
    }
    if r <= A.size() && A[r] > A[largest] {
        largest = r
    }
    if largest != i {
        swap(A[i], A[largest])
        Max_Heapify(A, largest)
}

上述代码的目的，就是时时刻刻维护A[Parent] > A[Child]这一条性质。

（继续借图说话，侵删）

下面给出C++代码实现：

int Left(int i){
    return 2*i;
}

int Right(int i){
    return 2*i+1;
}

int Parent(int i){
    return i/2;
}
void Adjustify(int A[], int i){  //下标为i的节点为根节点
    int l = Left(i);
    int r = Right(i);
    int largest = 0;
    if(l <= A.size() && A[l] > A[i]) //保证数组不越界
        largest = l;             //让此时的左孩子标记为兄弟双亲中最大值节点
    else
        largest = i;             //否则父节点依然是最大值节点
    if(r <= A.size() && A[r] > A[largest]) //继续判断右孩子和最大值节点哪个大
        largest = r;             //若右孩子大，则将右孩子标记为最大值节点
    if(largest != i){            //当最大值节点与父亲节点不是同一节点，则交换
        swap(A[i], A[largest]);  //此时保证父亲节点是最大值节点
        Adjustify(A, largest);   //递归，直到整个堆维护结束为止
    }
}

代码不难吧！于是，我们就需要在每一次对堆进行插入删除操作时维护一次堆。

---

堆的建立过程本质上就是插入数据的过程（自顶向下），亦或是数据堆积的过程（自底向上）：

void Build_Max_Heap(int A[]){
    int heapSize = A.size();
    for(int i = heapSize/2; i >= 0; i--){
        Adjustify(A, i);
    }
}

通过上述代码，我们可以知道这种建堆过程是自底向上建立的。

#include <iostream>
#include <algorithm>
using namespace std;
int Left(int i){
	return 2*i;
}

int Right(int i){
	return 2*i+1;
}

int Parent(int i){
	return i/2;
}
void Adjustify(int A[], int i){  //下标为i的节点为根节点
	int l = Left(i);
	int r = Right(i);
	int largest = 0;
	if(l <= 12 && A[l] > A[i]) //保证数组不越界
		largest = l;             //让此时的左孩子标记为兄弟双亲中最大值节点
	else
		largest = i;             //否则父节点依然是最大值节点
	if(r <= 12 && A[r] > A[largest]) //继续判断右孩子和最大值节点哪个大
		largest = r;             //若右孩子大，则将右孩子标记为最大值节点
	if(largest != i){            //当最大值节点与父亲节点不是同一节点，则交换
		swap(A[i], A[largest]);  //此时保证父亲节点是最大值节点
		Adjustify(A, largest);   //递归，直到整个堆维护结束为止
	}
}

void Build_Max_Heap(int A[]){
	int heapSize = 12;
	for(int i = heapSize/2; i >= 0; i--){
		Adjustify(A, i);
	}
}
int main(int argc, char *argv[]) {
	int A[] = {6,3,4,7,9,1,2,4,6,8,9,0};
	Build_Max_Heap(A);
	for(int i=0;i<12;i++){
		cout<<A[i]<<"  ";
	}
	cout<<endl;
	return 0;
}

由于我这是用C风格写的C++，为了不写printf，cout写法比较简单，所以没有用vector<int> A代替A[ ]。也因此，函数部分需要预先知道数组大小。如果不知道数组大小，还需另求。若用vector容器，可以直接调用函数求A的大小。

---

于是，这里给出最后的一些结论。。。。

维护堆时间复杂度为：O(lgn)

建堆过程时间复杂度为：O(n)

堆排序过程：O(nlgn)

希望各位看官老爷以后面试要记牢啊啊啊啊啊。