堆

最大堆：排序以及最小k个数

堆排序：不稳定，平均情况和最坏情况的时间复杂度O(nlogn),空间复杂度O(1)

void swap(int *a, int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

void heapDown(int *a, int n)
{
    if(n<=0) return;

    int max;
    int c=0;

    while(2*c<n)
    {
        if(2*c+1<n)
        {
            if(a[2*c+1]<a[2*c+2]) max=2*c+2;
            else max=2*c+1;
        }
        else max=2*c+1;

        if(a[c]<a[max]) swap(&a[c],&a[max]);
        else break;

        c=max;
    }
}

void heapUp(int *a, int n)
{
    if(n<=0) return;

    while(n)
    {
        if(a[n/2]<a[n]) swap(&a[n/2],&a[n]);
        else break;

        n=n/2;
    }
}

void heapSort(int *a, int n)
{
    if(n<=0) return;

    int i;

    for(i=1;i<n;i++) heapUp(a,i);

    for(i=n-1;i>=1;i--)
    {
        swap(&a[i],&a[0]);
        heapDown(a,i-1);
    }
}

void minK(int *a, int n, int k)
{
    if(n<=0) return;
    if(k<=0) return;

    int i;

    for(i=1;i<k;i++) heapUp(a,i);

    for(i=k;i<n;i++)
    {
        if(a[i]<a[0])
        {
            swap(&a[i],&a[0]);
            heapDown(a,k-1);
        }
    }
}