【算法与数据结构】堆排序&&TOP-K问题

//升序，建大堆
//O(N*logN)

//定义一个交换函数，用于交换两个元素的值
void Swap(int* px, int* py)
{
  int temp = *px;
  *px = *py;
  *py = temp;
}
//将以parent为根节点的子树进行向下调整，使其满足大堆的性质
void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1; //左孩子节点的下标
  while (child < n)
  {
    //找到左右孩子节点中较大的一个
    if (child + 1 < n && a[child + 1] > a[child])
    {
      child++;
    }
    //如果孩子节点的值大于父节点的值，则交换位置
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

//堆排序函数
void HeapSort(int* a, int n)
{
  //将数组a直接建堆，使其满足大堆的性质
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1; //用于记录堆的末尾位置
  while (end > 0)
  {
    //将堆顶元素与末尾元素交换位置，即将最大值放到末尾
    Swap(&a[0], &a[end]);
    //对除了末尾元素外的部分进行向下调整，使其满足大堆的性质
    AdjustDown(a, end, 0);
    end--;
  }

}
int main()
{
  int a[] = { 3,9,5,2,7,8,10,1,4 };
  printf("堆升序前\n");
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  //堆升序，建大堆
  HeapSort(a, sizeof(a) / sizeof(int));
  printf("\n堆升序后\n");
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;

}

void CreateNData()
{
  //造数据
  int n = 100000;
  srand(time(0));//使用时间作为随机数种子
  const char* file = "data.txt";//数据文件名
  FILE* fin = fopen(file, "w");//打开文件用于写入
  if (fin == NULL)//检查文件是否打开成功
  {
    perror("fopen error");//输出打开错误信息
    return;
  }

  for (int i = 0; i < n; ++i)//循环写入n行数据
  {
    int x = (rand() + i) % 1000000;//生成0-999999之间的随机数
    fprintf(fin, "%d\n", x);//写入一行数据
  }
  // 别忘了关闭文件哦
  fclose(fin);
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}


void AdjustDown(int* a, int n, int parent)
{ //a是数组指针,n是数组长度,parent是当前需要下调的父结点索引

  int child = parent * 2 + 1;
  //child表示父结点parent的左孩子结点索引,因为是完全二叉堆,可以通过parent和2计算得到

  while (child < n)
  {
    //如果左孩子存在

    if (child + 1 < n && a[child + 1] < a[child])
    {
      //如果右孩子也存在,并且右孩子值小于左孩子,则child指向右孩子
      child++;
    }
    if (a[child] < a[parent])
      //如果孩子结点值小于父结点值,则需要交换
    {
      Swap(&a[child], &a[parent]);
      //交换孩子和父结点
      parent = child;
      //父结点下移为当前孩子结点

      child = parent * 2 + 1;

      //重新计算新的左孩子结点索引

    }
    else
    {
      break;
    }
  }
}
void topk()
{
  printf("请输入k->");
  int k = 0;
  scanf("%d", &k);
  const char* file = "data.txt";
  //打开文件
  FILE* fout = fopen(file, "r");
  if (fout == NULL)
  {
    perror("malloc fail");
    return;
  }
  //临时变量读取文件数据 
  int val = 0;
  //分配内存用于保存最小堆
  int* minheap = (int*)malloc(sizeof(int) * k);
  if(minheap ==NULL)
  {
    perror("malloc fail");
    return;
  }
  //初始化堆,读取文件前k个数据构建最小堆
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minheap[i]);
  }
  
  //建个小堆
  for (int i = (k - 1 - 1) / 2; i >=0; i--)
  {
    AdjustDown(minheap, k, i);
  }

  int x = 0;
  while (fscanf(fout, "%d", &x) != EOF)
  {
    //读取剩余数据，比对顶的值大，就替换他进堆
    if (x > minheap[0])
    {
      //替换堆顶值,并调用下滤调整堆结构
      minheap[0] = x;
      AdjustDown(minheap, k, 0);
    }
  }

  for (int i = 0; i < k; i++)
  {
      //输出堆中保存的前k个最大值 
    printf("%d ", minheap[i]);
  }
  printf("\n");
  fclose(fout);

}

int main()
{
  CreateNData();
  topk();
}