数据结构-堆的实现及应用(堆排序和TOP-K问题)（下）

for (int i = 1; i < n; i++)
  {
    AdjustUp(arr, i, cmp_up);
  }
• 1

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, i, n, cmp_down);
  }

//向下调整算法
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(arr, i, n, cmp_down);
  }
//向上调整算法
  for (int i = 1; i < n; i++)
  {
    AdjustUp(arr, i, cmp_up);
  }

void HeapSort(int* a,int n)
{
  int i = 0;
  //这里用向下调整算法来建堆,因为时间复杂度只有O(N)
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

void HeapSort(int* a,int n)
{
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustUp(a, n, i);
  }
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustUp(a, end, 0);
    --end;
  }
}

假设有10亿个数据,内存存不下,数据在文件中
找出最大的前K个,  K==100
1.读取文件的前100个数据,在内存数组中建立一个小堆
2.再依次读取剩下的数据,跟堆顶数据比较,大于堆顶,就替换它进堆,向下调整
3.所有数据读取完毕,堆里面的数据就是最大的前100个

为什么不建议建大堆:
大堆只能找出最大的一个数,
而且最大的数会挡在根节点的位置,后面的数完全无法进堆,那就完蛋了
小堆的优势
而小堆的话,只有第K个大的数才会挡在根节点的位置,而更大的数会往堆的下面跑
时间复杂度O(N*logK),而且K相对于N来说可以忽略不计,所以可以认为是O(N)
时间复杂度:O(K),K:堆的大小,而K相对于N来说可以忽略不计,所以可以认为是O(1)

void Swap(int*p1,int*p2)
{
     int tmp =*p1;
     *p1 = *p2;
     *p2 = tmp;
}
//前k个数建大堆
//向下调整算法
 void AdjustDown(int*a,int n,int parent)
 {
     int minchild = parent*2+1;
     while(minchild<n)
     {
         if(minchild+1<n&&a[minchild+1]>a[minchild])
         {
             minchild++;
         }
         if(a[minchild]>a[parent])
         {
             Swap(&a[minchild],&a[parent]);
             parent = minchild;
             minchild = parent*2+1;
         }
         else
         {
             break;
         }
     }
 }
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
    if(k==0)
    {
        *returnSize=0;
        return NULL;
    }
    int* ret=(int*)malloc(sizeof(int)*k);
    for(int i=0;i<k;i++)
    {
        ret[i]=arr[i];
    }
    //前k个数建大堆
    for(int i=(k-1-1)/2;i>=0;i--)
    {
        AdjustDown(ret,k,i);
    }
    for(int i=k;i<arrSize;i++)
    {
        if(ret[0]>arr[i])
        {
            ret[0]=arr[i];
            AdjustDown(ret,k,0);
        }
    }
    *returnSize=k;
    return ret;
}

//创建一个文件，并且随机生成一些数字
void CreateDataFile(const char* filename, int N)
{
  FILE* Fin = fopen(filename, "w");
  if (Fin == NULL)
  {
    perror("fopen fail");
    exit(-1);
  }
  srand(time(0));
  for (int i = 0; i < N; i++)
  {
    fprintf(Fin, "%d ", rand() % 10000);
  }
}
void PrintTopK(const char* filename, int k)
{
  assert(filename);
  FILE* fout = fopen(filename, "r");
  if (fout == NULL)
  {
    perror("fopen fail");
    return;
  }
  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]);
  }
  //建k个数的堆
  for (int j = (k - 1 - 1) / 2; j >= 0; j--)
  {
    AdjustDown(minheap, j, k, cmp_down);
  }
  //读取后N-K个
  int x = 0;
  while(fscanf(fout,"%d",&x)!=EOF)
  {
    if (x > minheap[0])
    {
      minheap[0] = x;
      AdjustDown(minheap, 0, k, cmp_down);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", minheap[i]);
  }
  printf("\n");
  free(minheap);
  fclose(fout);
}
int main()
{
  //CreateDataFile("data.txt", 1000000);
  //找前10个最大的数
  PrintTopK("data.txt", 10);
  return 0;
}