二叉树-堆应用（1）

//堆排序:本质直接在数组里面排序
void test1(int* a, int size)
{
  //方法1的时间/空间复杂度都很低
  //方法2
  //1.向上调整建堆 建堆--建的小堆--降序 建大堆--升序
  for (int i = 0; i < size; i++)
  {
    AdjustUp(a, i);
  }
  //1.向下调整建堆
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i=0的时候到达根节点此时就是全部向下调整
  {
    Adjustdown(a, size, i);//这里的size不确定，但是肯定比size小所以取最大就size
  }
  //2.
  while (size)
  {
    //交换
    Swap(&a[0], &a[size - 1]);
    //向下调整(除去已经排序好的元素）
    Adjustdown(a, size-1, 0);
    //到达下一个交换的位置
    size--;
  }
}
int main()
{
  int a[10] = { 2,3,7,5,4,3,9,7,6,10 };
  int size = sizeof(a) / sizeof(a[0]);//10个数==最后一个数的下一个数的下标
  test1(a, size);
  //3.打印
  for (int i = 0; i < size; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

void CreateDate()//创造数据
{
  int n = 1000000;
  srand((unsigned int)time(NULL));//随机数的种子
  //打开文件
  const char* file = "data.txt";//文件指针
  FILE* fin = fopen(file, "w");//以写的形式打开文件状态指针
  if (fin == NULL)//打开失败
  {
    perror("fopen error");
    return;
  }
  //写文件
  for (int i = 0; i < n; i++)
  {
    int r = (rand() + i) % 1000000;
    fprintf(fin, "%d\n", r);
  }
  //关闭文件
  fclose(fin);
}
void test2(int K)
{
  //打开文件
  const char* file = "data.txt";//文件指针
  FILE* fout = fopen(file, "r");//以写的形式打开文件状态指针
  if (fout == NULL)//打开失败
  {
    perror("fopen error");
    return;
  }
  //读取文件
  //开辟数组空间存放小堆
  int* a = (int*)malloc(sizeof(int) * K);
  if (a == NULL)
  {
    perror("malloc error");
    return;
  }
  for (int i = 0; i < K; i++)
  {
    fscanf(fout, "%d", &a[i]);//读取放入数组
    AdjustUp(a, i);//建小堆
  }
  //一直读取并且比较
  int n = 0;
  while (fscanf(fout,"%d", &n) != EOF)
  {
    if (a[0] < n)
    {
      a[0] = n;
      Adjustdown(a, K, 0);
    }
  }
  //打印
  int i = 0;
  for (i = 0; i < K; i++)
  {
    printf("%d ", a[i]);
  }
  //释放空间/关闭文件
  free(a);
  fclose(fout);
}
int main()
{
  //CreateDate();//创造数据
  int K = 8;
  test2(K);//TopK问题--小堆--取前K个最大的数
  return 0;
}

void CreateDate()//创造数据
{
  int n = 1000000;
  srand((unsigned int)time(NULL));//随机数的种子
  //打开文件
  const char* file = "data.txt";//文件指针
  FILE* fin = fopen(file, "w");//以写的形式打开文件状态指针
  if (fin == NULL)//打开失败
  {
    perror("fopen error");
    return;
  }
  //写文件
  for (int i = 0; i < n; i++)
  {
    int r = (rand() + i) % 1000000;
    fprintf(fin, "%d\n", r);
  }
  //关闭文件
  fclose(fin);
}