1.堆排

 

             堆排是利用堆来进行排序的，分为向上调整建堆，和向下调整建堆

              堆分为大堆和小堆，大堆一般排升序，小堆排降序

    向下调整建堆：

            把数据中每个父亲节点全调整一遍（从后到前的父亲节点）

            这样就会得到一个有序的堆

排序

  建完堆之后，首位为最大项，让首位和末尾交换，再向下调整（不过范围是末尾的前一位）；

 依次直到剩下首元素，升序就排好了

//交换
void swap(int* A, int* B)
{
    int temp = *A;
    *A = *B;
    *B = temp;
}
//向下调整
void AdjustDown(int* a, int n, int parents)
{
    int child = parents * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }
        if (a[parents] < a[child])
        {
            swap(parents + a, child + a);//交换程序
            parents = child;
            child = parents * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//排序
void HeapSort(int* a, int n)
{
    //建堆；
    for (int i = (n - 1 - 1) / 2;i >= 0;--i)
    {
        AdjustDown(a, n, i);
    }
    //排序；
    for (int i = 0;i < n-1;i++)
    {
        swap(a, a + n - 1 - i);
        AdjustDown(a, n- 1- i, 0);
    }
}

 2.Topk.

  Topk是寻找最大或最小的前k位，如果你把数据排序后寻找的话效率很低

 所以这里我们只建k的元素的堆（找最大建小堆，找最小建大堆），

 若我们找最大前k项，就建一个k元素的小堆再用堆顶的元素与剩下的元素对比

 若大于堆顶元素则于堆顶元素交换,再进行向下调整，这样会发现堆内的元素再

 增大，最后存的就是最大前k项（最小前k项同理）.

//交换
void swap(int* A, int* B)
{
    int temp = *A;
    *A = *B;
    *B = temp;
}
//向下调整
void AdjustDown(int* a, int n, int parents)
{
    int child = parents * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child])
        {
            ++child;
        }
        if (a[parents] > a[child])
        {
            swap(parents + a, child + a);//交换程序
            parents = child;
            child = parents * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapTopk(int* a, int n, int k)
{
   //建堆
    for (int i = (k - 1) / 2;i >= 0;--i)
    {
        AdjustDown(a, k, i);
    }
    //排k堆
    for (int i = k;i < n;i++)
    {
        if (a[i] > a[0])
        {
            swap(a + i, a);
            AdjustDown(a, k, 0);
        }
    }
}