【数据结构】堆综合的运用

一，运用堆结构进行排序

       当我们用堆结构进行排序时，首先要明确的是升序排列要建大堆，降序排列要建小堆，不是说升序建小堆就不行，降序建大堆就不行，而是如果运用这种建堆方式进行排序的话效率会比较低，下面我会跟大家详细分析。

       首先，我们来回顾一下堆的概念，大堆结构：双亲结点>=孩子结点。小堆结构：双亲结点<=孩子结点。其中，根节点是所有结点的"祖宗"，也就是在大堆中，根节点是在堆中最大的数据，在小堆中，根节点是在堆中最小的数据。排升序时，当我们运用建小堆思想，虽然第一个数据已确定序列位置，但后面的数据要想确定序列位置就必须对除去上一次数据外剩下的元素再次建堆，也就是建一次小堆相当于排好一个数据的序列位置。排降序时运用大堆同理。此时的时间效率为O((n*logn)*n)。由此可见，此种方法效率太低。

       当升序用建大堆思想时，大堆中根结点是最大数据，升序序列中最后的数据都是最大的数据，我们只需在大堆中将首元素与尾元素进行交换后即可确定最后一个元素的序列位置，然后再除去大堆中最后一个元素将根结点运用向下调整算法进行调整，这将又得到除去最后一个元素的大堆，以次不断循环，最终将有序。由此可见，大堆排升序是从后到前的排序。

       降序用小堆的思想与之同理，都是先建立堆，然后不断交换确定数据序列位置，都是从后到前的排序。具体代码如下：

运用大堆排升序：

void Swap(int* x, int* y) {
   int t = *x;
   *x = *y;
   *y = t;
}
void AdjustUp(int* a, int child) {
   assert(a);
   int parent = (child - 1) / 2;
   while (parent >= 0) {
      //调整建大堆
       if (a[parent] < a[child]) {
           Swap(a + parent, a + child);
           child = parent;
           parent = (child - 1) / 2;
       }
       if (a[parent] >= a[child]) {
           return;
       }
   }
}
void AdjustDown(int* a, int n, int parent) {
   assert(a);
   int child = parent * 2 + 1;
   while (child < n) {
       //调整建大堆
       if (child + 1 < n && a[child] < a[child + 1]) {
           child++;
       }
       if (a[child] > a[parent]) {
           Swap(a + child, a + parent);
           parent = child;
           child = parent * 2 + 1;
       }
       if (a[child] <= a[parent]) {
           return;
       }
   }
}
void HeadSort(int* a, int n) {
   //运用向上调整算法建大堆
   for (int i = 1; i < n; i++) {
       AdjustUp(a, i);
   }
   //end是堆中最后一个元素的下标
   int end = n - 1;
   while (end > 0) {
      //将堆中最大数据排到最后
       Swap(&a[0], &a[end]);
       //将end个数据建成堆
       AdjustDown(a, end, 0);//因为根节点的左右子树都可看成大堆，所以只要向下调节根结点就可使end个数据成为大堆
       //后面已排好了一个数据，继续将剩下的数据建堆排序即可
       end--;
   }
}

运用小堆排降序

void Swap(int* x, int* y) {
   int t = *x;
   *x = *y;
   *y = t;
}
void AdjustUp(int* a, int child) {
   assert(a);
   int parent = (child - 1) / 2;
   while (parent >= 0) {
       //调整建小堆
       if (a[parent] > a[child]) {
           Swap(a + parent, a + child);
           child = parent;
           parent = (child - 1) / 2;
       }
       if (a[parent] <= a[child]) {
           return;
       }
   }
}
void AdjustDown(int* a, int n, int parent) {
   assert(a);
   int child = parent * 2 + 1;
   while (child < n) {
      //调整建小堆
       if (child + 1 < n && a[child] > a[child + 1]) {
           child++;
       }
       if (a[child] < a[parent]) {
           Swap(a + child, a + parent);
           parent = child;
           child = parent * 2 + 1;
       }
       if (a[child] >= a[parent]) {
           return;
       }
   }
}
void HeadSort(int* a, int n) {
  //运用向上调整算法建小堆
   for (int i = 1; i < n; i++) {
       AdjustUp(a, i);
   }
   //end是堆中最后一个元素的下标
   int end = n - 1;
   while (end > 0) {
       //将堆中最小数据排到最后
       Swap(&a[0], &a[end]);
      //将end个数据建成堆
       AdjustDown(a, end, 0);//因为根节点的左右子树都可看成小堆，所以只要向下调节根结点就可使end个数据成为小堆
       //因为后面排好了一个数据，继续将剩下的数据建堆排序即可
       end--;
   }
}

效率分析：

       我们先观察前面的建堆效率：时间复杂度：O(nlogn)     空间复杂度：O(1)

       在后面排序时，每当确定一个数据的序列位置时就要运用调整算法进行调整一次，所以，要对n个数据排序时的时间复杂度：O(nlogn)   空间复杂度：O(1)。因此，运用堆结构排序的整体效率：时间复杂度：O(nlogn)   空间复杂度：O(1)。

二，经典的Topk问题

      Topk问题：假设有100万个数据(也可以是1千万，1亿个数据，只要数据足够大即可)，而这些数据内存又存储不下，所以要靠文件来进行存储，在文件中，我们需要找出最大的前k个数据。

       此问题可以用堆结构来完成，具体步骤如下：

       1，读取文件的前k个数据，在内存数组中建立一个大小为k的小堆。

       2，再依次读取剩下的数据与堆顶数据比较，大于堆顶就替换这个数据进堆，然后向下调整，调整后的数据仍为堆，即堆顶数据是堆中最小的数据。

       3，所有数据读完，堆里面数据就是最大的前k个数据。

       首先，我们先造出这么多个数据，将其写入文件中。

//str是文件的路径
void CreatData(char* str) {
  FILE* file = fopen(str, "w");
  if (file == 0) {
    perror("fopen");
    exit(-1);
  }
  //造出1000000个数据，也可以造出更多
  srand(time(0));
  for (int i = 0; i < 1000000; i++) {
    //造出范围在[1, 1000]的数据
    int n = (rand() + i) % 1000 + 1;
    fprintf(file, "%d\n", n);
  }
  fclose(file);
}

       然后，先建立起小堆结构，再将前k个数据放入小堆中，最后遍历文件数据进行交换。

void CreatHeap(char* str, int k) {
  //建立堆结构并初始化
  int* a = (int*)malloc(sizeof(int) * k);
  if (a == 0) {
    perror("malloc");
    exit(-1);
  }
  memset(a, 0, sizeof(int) * k);
  //先将文件中的前k个数据放到堆中，将其调成小堆
  FILE* file = fopen(str, "r");
  if (!file) {
    perror("fopen");
    exit(-1);
  }
  for (int i = 0; i < k; i++) {
    fscanf(file, "%d", a + i);
  }
  for (int i = (k - 2) / 2; i >= 0; i--) {
    AdjustDown(a, k, i);
  }
  //然后遍历文件中剩下数据
  int x = 0;
  while (fscanf(file, "%d", &x) != EOF) {
    if (x > a[0]) {
      Swap(&x, &a[0]);
      AdjustDown(a, k, 0);
    }
  }
  //输出
  for (int i = 0; i < k; i++) {
    fprintf(stdout, "%d ", a[i]);
  }
  puts("");
  free(a); 
  fclose(file);
}

整套代码如下(我们将k设置为100，即从100万个数据选出100个最大数)：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
void Swap(int* x, int* y) {
  int t = *x;
  *x = *y;
  *y = t;
}
void AdjustUp(int* a, int child) {
  assert(a);
  int parent = (child - 1) / 2;
  while (parent >= 0) {
    if (a[parent] > a[child]) {
      Swap(a + parent, a + child);
      child = parent;
      parent = (child - 1) / 2;
    }
    if (a[parent] <= a[child]) {
      return;
    }
  }
}
void AdjustDown(int* a, int n, int parent) {
  assert(a);
  int child = parent * 2 + 1;
  while (child < n) {
    if (child + 1 < n && a[child] > a[child + 1]) {
      child++;
    }
    if (a[child] < a[parent]) {
      Swap(a + child, a + parent);
      parent = child;
      child = parent * 2 + 1;
    }
    if (a[child] >= a[parent]) {
      return;
    }
  }
}
//str是文件的路径
void CreatData(char* str) {
  //注意："w"表示以写入方式打开文件并清空文件内容
  FILE* file = fopen(str, "w");
  if (file == 0) {
    perror("fopen");
    exit(-1);
  }
  //造出1000000个数据，也可以造出更多
  int n = 1000000;
  srand(time(0));
  for (int i = 0; i < n; i++) {
    //造出范围在[1, 1000]的数据
    int n = (rand() + i) % 1000 + 1;
    fprintf(file, "%d\n", n);
  }
  fclose(file);
}
void CreatHeap(char* str, int k) {
  //建立堆结构并初始化
  int* a = (int*)malloc(sizeof(int) * k);
  if (a == 0) {
    perror("malloc");
    exit(-1);
  }
  memset(a, 0, sizeof(int) * k);
  //先将文件中的前k个数据放到堆中，将其调成小堆
  FILE* file = fopen(str, "r");
  if (!file) {
    perror("fopen");
    exit(-1);
  }
  for (int i = 0; i < k; i++) {
    fscanf(file, "%d", a + i);
  }
  for (int i = (k - 2) / 2; i >= 0; i--) {
    AdjustDown(a, k, i);
  }
  //然后遍历文件中剩下数据
  int x = 0;
  while (fscanf(file, "%d", &x) != EOF) {
    if (x > a[0]) {
      Swap(&x, &a[0]);
      AdjustDown(a, k, 0);
    }
  }
  //输出
  for (int i = 0; i < k; i++) {
    fprintf(stdout, "%d ", a[i]);
  }
  puts("");
  free(a); 
  fclose(file);
}
//删除路径在str中的文件
void DeleteFile(char* str) {
  if (remove(str) != 0) {
    fprintf(stdout, "无法删除文件\n");
  }
  else {
    fprintf(stdout, "文件已删除\n");
  }
}
int main() {
  //创建巨多数据，将其输出到文件中
  CreatData("E:\\test.txt");
  //k为100,建立大小为100的小堆，并将文件中最大的前100个数据放入小堆中
  CreatHeap("E:\\test.txt", 100);
  //删除文件
  DeleteFile("E:\\test.txt");
  return 0;
}

效率分析：

       从以上中不难发现：时间复杂度：O(n*logk)。空间复杂度：O(k)

补：从以上两个运用不难发现，堆结构的效率很高，在今后遇到的复杂问题中，我们都可运用高效率的堆结构来进行优化。