1.1 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

• 升序：建大堆
• 降序：建小堆

1. 利用堆删除思想来进行排序

#include<stdio.h>
void Swap(int* e1, int* e2)
{
    int tem = *e1;
    *e1 = *e2;
    *e2 = tem;
}
void AdjustDown(int* a, int n, int parent)
{
    int midchild = parent * 2 + 1;
    while (midchild < n)
    {
        //建小堆找小的那个孩子，建大堆找的大的孩子
        if (midchild + 1 < n && a[midchild] < a[midchild + 1])
        {
            midchild++;
        }
        if (a[parent] < a[midchild])
        {
            Swap(&a[parent], &a[midchild]);
            parent = midchild;
            midchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int* a, int n)
{
    //建堆
    int i = 0;
    for (i = (n-2)/2; i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }
    
    for (i = 0; i < n; i++)
    {
        Swap(&a[0], &a[n - i - 1]);
        AdjustDown(a, n - i-1, 0);
    }
}


int main()
{
    int arr[] = { 30,60,12,40,8,10,70 };
    int n = sizeof(arr) / sizeof(arr[0]);
    HeapSort(arr,n);
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

1.2 TOP-K问题

• TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆（适用于数据量较小的时候）

.

1. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素注意：当数据量大的时候最适合用这种方法

• 实例：我们在10000个数选出最大的前10个元素

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void Swap(int* e1, int* e2)
{
    int tem = *e1;
    *e1 = *e2;
    *e2 = tem;
}

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
    int midchild = parent * 2 + 1;
    while (midchild < n)
    {
        //建小堆找小的那个孩子，建大堆找的大的孩子
        if (midchild + 1 < n && a[midchild] > a[midchild + 1])
        {
            midchild++;
        }
        if (a[parent] > a[midchild])
        {
            Swap(&a[parent], &a[midchild]);//交换
            parent = midchild;
            midchild = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


//咱们求最大的前10个数
void PrintTopK(int* a, int n, int k)
{
    // 1. 建堆--用a中前k个元素建小堆
    int i = 0;
    for (i = (k - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(a, k, i);
    }
    
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    for (i = k; i < n; i++)
    {
        if (a[i] > a[0])//建小堆的意义在这，把大于堆顶的元素入堆
        {
            a[0] = a[i];
            AdjustDown(a, k, 0);//重新将数组首元素这个位置向下调整，使其成为小堆
        }
    }
    printf("\n前Top10分别为：");
    for (i = 0; i < k; i++)
    {
        printf("%d ", a[i]);
    }
}

void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand( (unsigned int )time(0));
    for (int i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;//制造10000个小于1000000的随机数
    }
    //手动将大于1000000的数加上，不出意外，等下选出的就是这些数，因为他们是前top10
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2335] = 1000000 + 6;
    a[9999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
    PrintTopK(a, n, 10);
    free(a);
}


int main()
{
    TestTopk();

    return 0;
}