有一个面试题，100w个数中找到最大的100个数。 

解决方式是，用一个100个容量的最小堆， 这100个数总数目前已知的最大的100个，而且 

堆顶是小的， 在继续遍历时候，只和堆定比较， 如果这个数，比堆顶的大， 就把这个数加入 

这个堆。 

当遍历完成后，这个最小堆中的数，就是最大的100个数了。

当理解了这个， 我还有一个疑惑， 什么是最小堆。

http://blog.csdn.net/genios/article/details/8157031

学习了这个篇帖子。 受益匪浅。 文章写的很好， 一开始很难理解，跟着模拟了一下，

关键是要自己模拟程序，去移动一下 这个树，才理解。




typedef struct heap HEAP;
struct heap {
     int arr[127];
     int size;
};

void insert(HEAP *h,int n){
       int sz = h->size++;
       printf("%d --- %d\n",sz,n);
       while(sz>0){
            if(n < h->arr[(sz-1)/2]){//若改成 > 则为大根堆
                h->arr[sz] = h->arr[(sz-1)/2];
                sz = (sz-1)/2;
            }else{
                h->arr[sz] = n;
                return;
            }
       }
       h->arr[0] = n;
}

void delete(HEAP *h){
       h->size--;
       h->arr[0] = h->arr[h->size];
       h->arr[h->size] = 0;
       int i = 1,cv = h->arr[0],tmp;
       while(i < h->size){
               if(i < h->size-1 && h->arr[i] > h->arr[i+1])
                      i++;
               if(h->arr[i] < cv){
                      h->arr[(i-1)/2] = h->arr[i];
                      h->arr[i] = cv;
                      i = i*2 + 1;
               }else{
                      return;
               }
       }
}

下面这个是我自己改的，上面的是 wikipedia上copy的



#include <iostream>

typedef struct heap HEAP;

struct heap
{
    int arr[100];
    int size;
};


//将数字num 插入 最小堆
//游标 比 位置 小一
void insert(HEAP *h, int num)
{

    int sz = h->size;
    h->size++;

    while( sz >0 ){
        if(num > h->arr[(sz-1)/2]){
            h->arr[sz] = num;
            return;
        }else{
            h->arr[sz] = h->arr[(sz-1)/2]; 
            sz = (sz-1)/2;
        }   
    }   

    h->arr[0] = num;

}




void c_delete(HEAP *h) 
{
    h->size--;
    h->arr[0] = h->arr[h->size];
    h->arr[h->size] = 0;

    int i=1;
    int cv = h->arr[0];

    while(i<h->size){
        if(cv < h->arr[i] && cv < h->arr[i+1]){
            return ;
        }   

        if(h->arr[i] > h->arr[i+1])
            i++;
        else{
            h->arr[(i-1)/2] = h->arr[i];
            h->arr[i] = cv;
            i = i*2 +1;
        }
    }
}


int main()
{
    return 0;
}

堆的实现

堆的本质是一二叉树，并且是一颗完全二叉树。

堆分为大堆和小堆，大堆就是在堆顶的元素的值是这个完全二叉树中的最大值，小堆刚好相反，是最小值。在树这个数据结构定义的时候是递归定义的所以也就满足，一个树中子数的更节点是最大或者最小（取决与建立大堆还是小堆）。



堆的建立

堆的建立过程是一个进行比较的过程，也就是说，每次插入一个元素，就需要对堆进行调整，怎么调整？当然在插入的时候，我们就已经确定需要建立大堆还是小堆，所以我们在插入的时候，每次都插入到堆的尾部，应为堆是一个完全二叉树，所以，我们插入到尾部后就需要和父节点的值进行比较，再进行调换，如果发现不用调换就说明插入完成。

堆的建立是基于一个顺序表的数据。

具体是的实现：

void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 调整堆
void AdjustUp(int arr[], size_t size, size_t index)
{
    if (arr == NULL)
    {
        return;
    }
    size_t child = index;
    size_t parent = (size - 1 - 1) / 2;
    while (child > 0)
    {
        if (arr[child] < arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
        }
        // 因为是尾部插入然后上移，当上移到parent < child时候，
        // 就需要停止，不然会继续向上判断。
        else 
        {
            break;
        }
        child = parent; 
        parent = (child-1) / 2; 
    }
}

void CreateHeap(int arr[], size_t size)
{
    for (int i = 0; i < size; ++i)
    {
        // 在堆尾部插入，每次堆增加1
        AdjustUp(arr, i,i);
    }
}



取堆顶元素

我们建堆的目的一般都是为了排序或者取最大或者最小的数值，那么就需要取堆的顶部元素。我们来实现取堆顶元素



// 因为我们用到是c语言，所以我们用了输出型参数value
int HeapFindRoot(int arr[], int *value)
{
    if (arr == NULL || value == NULL)
    {
        // 取失败
        return 0;
    }
    *value = arr[0];
    return 1;
}


取完堆顶元素，那么就要删除，在堆排序中，正是删除堆顶元素，然后在对堆进行调整就会得到新的堆顶元素。 

代码：



删除堆顶元素



// 下沉
void AdjustDown(HeapType arr[],size_t size, size_t index)
{
    if (arr == NULL)
    {
        return;
    }
    size_t lchild = index * 2 + 1;
    while (lchild < size)
    {
        // 如果是右孩子小于左孩子，那么把下标为右孩子赋给左孩子下标。
        if ((lchild + 1 < size) && cmp(arr[lchild + 1], 
        \arr[lchild]))
        {
            lchild = lchild + 1;
        }
        // 把孩子中小的一个与父节点值比较，如果父值大，
        //子小，那么交换。否则跳出循环。
        if (cmp(arr[lchild], arr[index]))
        {
            Swap(&arr[lchild], &arr[index]);
        }
        else
        {
            break;
        }
        // 更新index和孩子节点下标。
        index = lchild;
        lchild = index * 2 + 1;
    }
}

// 删除堆顶元素。
void HeapErase(int arr[],size_t size)
{
    if (arr == NULL)
    {
        return;
    }
    Swap(&arr[0], &arr[size-1]);
    --size;
    size_t index = 0;
    AdjustDown(arr, size, index);
}

以上就是堆数据结构都是用int型。我们在实际中也可以是一个结构体，也可以是进程，进程的优先调度算法就是用一个堆的数据结构来实现。



堆排序

堆排序是一种时间复杂度为O(nlogn)算法。空间复杂度为O(n)的算法。



下沉
void AdjustDown(HeapType arr[],size_t size, size_t index)
{
    if (arr == NULL)
    {
        return;
    }
    size_t lchild = index * 2 + 1;
    while (lchild < size)
    {
        // 如果是右孩子小于左孩子，那么把下标为右孩子赋给左孩子下标。
        if ((lchild + 1 < size) && cmp(arr[lchild + 1], 
        \arr[lchild]))
        {
            lchild = lchild + 1;
        }
        // 把孩子中小的一个与父节点值比较，如果父值大，
        //子小，那么交换。否则跳出循环。
        if (cmp(arr[lchild], arr[index]))
        {
            Swap(&arr[lchild], &arr[index]);
        }
        else
        {
            break;
        }
        // 更新index和孩子节点下标。
        index = lchild;
        lchild = index * 2 + 1;
    }
}

// 时间复杂度为O(N * LogN)
void HeapSort1(HeapType arr[], size_t size)
{
    if (arr == NULL || size <= 1)
    {
        return;
    }
    // 先减一是计算时是从0开始，第二个是child推导parent公式
    size_t begen = (size - 1 - 1)/2;
    // 这里采用下沉建树
    for (; begen > 0; --begen)
    {
        AdjustDown(arr, size, begen);
    }
    AdjustDown(arr, size, 0); // 这是处理0这种情况
    size_t heap_size = size;
    while (heap_size > 0)
    {
        Swap(&arr[0], &arr[heap_size - 1]);
        --heap_size;
        AdjustDown(arr, heap_size, 0);
    }
}

参考资料1，写的挺不错

还有这个
假设你已经学建立最大堆或者最小堆
那么怎么利用最大堆来进行堆排序呢？

1：因为堆顶元素一定是最大值，然后将其输出

2：吧堆顶元素与堆的最后一个元素交换，

删除堆的最后一个元素，

将顶元素进行下移操作，这样又可以保证堆顶元素是最大值

3：重复操作1和2直到结束
#include<iostream>
#include<algorithm>
#include<random>
#include<time.h>
using namespace std;
int a[100];
int h[100];
int maxn;

void heapDown(int k) {
	while ( (k=2*k)<= maxn ) {
		if (k + 1 <= maxn && h[k + 1] > h[k])
			k++;
		if(h[k]>h[k/2] ) 
			swap(h[k], h[k / 2]);
		else break;
	}
}
void heapUp(int k) {
	while (k > 1) {
		if (h[k] > h[k / 2])
			swap(h[k], h[k / 2]),
			k /= 2;
		else break;
	}
}
void insertHeap(int k) {
	h[k] = a[k];
	heapUp(k);
}
void makeHeap() {
	for (int i = 1;i <= maxn;i++) {
		insertHeap(i);
	}
}
void heapSort() {
	while (maxn) {
		cout << h[1] << " ";
		swap(h[1], h[maxn]);
		maxn--;
		heapDown(1);
	}
}
int main()
{
	srand((unsigned)time(NULL));
	cin >> maxn;
	int n = maxn;
	for (int i = 1;i <= maxn;i++) {
		a[i] = rand() % 10000;
		makeHeap();
	}
	heapSort();

}

堆排序算法是建立在堆这种数据结构的基础上，其实堆听着很高端，其实很简单，就是一个二叉树，但是又特殊条件，就是其父节点比孩子节点都大（或都小）的堆称为最大堆（最小堆），瞬间感觉很简单了，最简单的保存方法就是直接用数组来保存。 

给出一组数，我们要使用堆排序，首先需要建堆，但是这一组数首先肯定是不满足上面堆的性质的，所以我们需要调整，让他满足堆得性质，变成一个堆，怎么调整呢？拿最大堆来说，就是对于一个节点，我们判断其孩子是否有比父亲节点大的，有的话，交换这两个值，这样父亲就比孩子都大了，当然交换完了之后可能以这个孩子为根节点的子树又不满足对性质了，继续交换直到都满足，为了减少交换的次数，我们可以从离叶子节点最近的节点开始交换，一层一层直到根节点。 

比如这样一组数a[]={16,7,3,20,17,8}，我们建堆 


然后依次调整 


这样一个堆就建立起来了。剩下的事情就很简单了 

有了堆之后我们很容易发现堆有一个很美好的性质，就是根节点的值闭锁所有的值都大（小），那么我们第 i 次选择根节点，放入数组第【n-i+1】，然后把第【n-i+1】的值放到根节点，调整堆，经过n次之后就是一个有序的了。过程如下1 


（图片非原创，有版权问题请联系我删除） 

堆排序被归类到选择排序里面，因为其思想和选择排序的思想是一样的，从剩下的数组里面选择一个最大的（最小的），放到排好序的位置，然后继续选择，只是选择排序选择一次的复杂度是O（n），这里选择是O（1），但是选择完了需要调整，调整的复杂度是log（n），所以总的复杂度是O（n*logn）。 

其实堆的另一个很常用的用法就是优先队列，所以大家可以看出来优先队列的复杂度了，每插入一个元素是O（logn），取出时O（1），这样大家就可以自己实现优先队列了

代码：



#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1001000;
int a[N];

void Balance(int x,int n)
{
    int l = x+x;
    int r = x+x+1;
    int mid = x;
    if(l<n && a[l]>a[mid])
        mid = l;
    if(r<n && a[r]>a[mid])
        mid = r;
    if(x!=mid)
    {
        swap(a[x],a[mid]);
        Balance(mid,n);
    }
}

void Heap_Sort(int n)
{
    for(int i=n/2-1;i>=0;i--)  //首先调整堆
        Balance(i,n);
    for(int i=n-1;i>=0;i--)
    {
        swap(a[i],a[0]);
        Balance(0,i);
    }
}

int main()
{
    //freopen("Input.txt","r",stdin);
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        Heap_Sort(n);
        for(int i=0;i<n;i++)
            printf("%d ",a[i]);
        puts("");
    }
    return 0;
}