堆排序算法和基于其思路的“超大数据寻找排名前k”问题的解决办法

最近封校封的闷得难受，便在食堂坐了一下午，，，本来是想好好写高数的，结果突然想到了自己没总结完的堆的使用---前k名问题，便连复习带补充的用演草纸写了一份，，，存在这里供大家参考吧。

可能在写的过程中有不严谨的地方，如果大家发现，还望不客气的批评指正，感谢！（跪） 

写的有点快，字比较丑，见谅~~ 

  本来是手撸了代码的，不想再敲一遍了，但由于：，以及当时写的太快，手撸代码部分有几处错误，于是功利的我~，又敲了一份代码，并优化了一下：

#include 
using namespace std;

typedef int Heaptype;//方便修改数据类型
typedef int Nowtype;//方便修改数据范围

void swap(Heaptype* a, Heaptype* b);//交换函数
void Down_ajm(Heaptype* arr, Nowtype parent, Nowtype size, bool ins);//向下调整函数
void HeapSort(Heaptype* arr, Nowtype size, bool ins);//堆排序函数
Heaptype* Topk_s(Heaptype* arr, Nowtype n, Nowtype k, bool ins);//前k名问题函数

int main(){
    //测试数据2 7 5 1 8 4 9 3 0 6
    Heaptype* arr = (Heaptype*)malloc(sizeof(Heaptype) * 1);
    cout << "请输入数据，用空格隔开，输入Ctrl+Z结束:" << 'n';
    Nowtype counter = 0;
    int lownum = 0;
    while (true) {
        if (cin >> lownum) {
            arr[counter] = lownum;
            counter++;
            arr = (Heaptype*)realloc(arr, sizeof(Heaptype)*(counter + 1));
        }
        else break;
    }
    cin.clear();//Ctrl+Z后需要复位流才能继续输入
    char rubbish = getchar();//吃掉垃圾值
    cout << 'n' <<"请输入要找前几个数（请输入大于0的数，这样才有意义）：";
    Nowtype k;
    cin >> k;
    cout << 'n' << "请输入是要找前" << k << "大还是前" << k << "小，前者请输入0，后者请输入1： ";
    bool ins;
    cin >> ins;
    Heaptype* target = Topk_s(arr, counter, k, ins);
    for (Nowtype i = 0; i < k; i++) {
        cout << target[i] << " ";
    }
    return 0;
}
void swap(Heaptype* a, Heaptype* b) {//交换函数
    Heaptype t = *a; *a = *b; *b = t;
}
void Down_ajm(Heaptype* arr, Nowtype parent, Nowtype size, bool ins) {//ins=0，构建小顶堆；ins=1，大顶堆
    Nowtype child = parent * 2 + 1;
    while (child < size) {
        bool t = 0;
        if (child + 1 < size) {
            t = ins == 0 ? (arr[child + 1] < arr[child]) : (arr[child + 1] > arr[child]);
        }
        if (child + 1 < size && t) {//标记较小/较大的子节点
            child++;
        }
        bool s = ins == 0 ? (arr[child] < arr[parent]) : (arr[child] > arr[parent]);
        if (s) {//符合条件就交换父子节点，并更新他们
            swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}
void HeapSort(Heaptype* arr, Nowtype size, bool ins) {//ins=0，从大到小，=1从小到大
    for (Nowtype i = (size - 1 - 1) / 2; i >= 0; i--) {
        Down_ajm(arr, i, size, ins);//先建小/大顶堆
    }
    Nowtype end = size - 1;
    while (end) {
        swap(&arr[0], &arr[end]);//交换顶节点与尾结点
        Down_ajm(arr, 0, end, ins);//并维持堆的结构
        end--;//锁定尾部数据
    }
}
Heaptype* Topk_s(Heaptype* arr, Nowtype n, Nowtype k, bool ins) {//ins=0,前k大；ins=1，前k小
    Heaptype* k_num = (Heaptype*)malloc(sizeof(Heaptype) * k);//用来存前k个数
    for (Nowtype i = 0; i < k; i++) {//录入数据
        k_num[i] = arr[i];
    }
    for (Nowtype i = (k - 1 - 1) / 2; i >= 0; i--) {//建立小/大顶堆
        Down_ajm(k_num, i, k, ins);
    }
    for (Nowtype i = k; i < n; i++) {//求前k大就建立小顶堆，反之建立大顶堆
        //这个原理就是不断更新前k个数的最小值（或最大值），想想就明白了
        bool t = ins == 0 ? (arr[i] > k_num[0]) : (arr[i] < k_num[0]);
        if (t) {
            k_num[0] = arr[i];//赋值
            Down_ajm(k_num, 0, k, ins);//维持堆的结构
        }
    }
    HeapSort(k_num, k, ins);//排序
    return k_num;//返回装有前k大（或小）的数的数组的指针
}