• 初阶数据结构学习记录——아홉 二叉树和堆（2）

    目录

    一、堆创建

    二、堆排序

    三、TOPK问题

    一、堆创建

    接着上一篇

    之前写过一些关于堆的代码，向下调整，向上调整算法，以及常用的几个函数。这一篇继续完善堆，难度也会有所上升。先来看上一篇文末提到的创建堆算法。

    首先要有空间，要有数据，之后再形成堆。我们可以malloc一块空间，数据也可push或者创建一个数组然后拷贝过来，不过面对一个不成规则的数据如何把他们做成堆？直接用向上或向下调整都不能做到，我们可以用Init初始化后，挨个push，它会自动地扩容然后向上调整做成堆，但是实际上向下调整效率更高，下面会验证，上一篇的pop函数中，把尾部的数字提到根部后，它的左右子树都是大堆，这时用向下调整就很合适。但是现在面临的是无规则的一个数组，左右子树也不确定是不是大堆。所以得创造出两个大堆。左右子树的数字都不少，应该如何调？现在我们的树是这样的

    15和19这两棵子树要调整，我们就大事化小，一部分一部分地调整，先想一下最容易找到的一个位置，就是尾部位置，也就是37，先调整37和28的关系，然后把18这棵子树的关系也调整一下，再调整19的，再调整15的，最后调整27的。37的下标是n - 1，而28则是(n - 1 - 1) / 2，所以最一开始从28这个位置开启循环，28的下标-1就是18，-1就是19，再-1就是15，所以就能一步步调整。

    1. void AdjustDown(HPDataType* a, int n, int parent)
    2. {
    3.     int child = parent * 2 + 1;
    4.     while (child < n)
    5.     {
    6.         //确认child指向大的那个孩子并且child要小于size
    7.         if (child + 1 < n && a[child + 1] > a[child])
    8.         {
    9.             ++child;
    10.         }
    11.         if (a[child] > a[parent])
    12.         {
    13.             Swap(&a[child], &a[parent]);
    14.             parent = child;
    15.             child = parent * 2 + 1;
    16.         }
    17.         else
    18.         {
    19.             break;
    20.         }
    21.     }
    22. }
    23.  
    24. void HeapCreate(HP* php, HPDataType* a, int n)
    25. {
    26.     assert(php);
    27.     php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    28.     if (php->a == NULL)
    29.     {
    30.         perror("realloc fail");
    31.         exit(-1);
    32.     }
    33.     memcpy(php->a, a, sizeof(HPDataType) * n);
    34.     php->size = php->capacity = n;
    35.  
    36.     // 建堆算法
    37.     for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    38.     {
    39.         AdjustDown(php->a, n, i);
    40.     }
    41. }
    42.  
    43. void TestHeap3()
    44. {
    45.     int arr[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
    46.     HP hp;
    47.     HeapCreate(&hp, arr, sizeof(arr) / sizeof(int));
    48.     HeapPrint(&hp);
    49.     HeapDestroy(&hp);
    50. }

    测试一下

     成功创建。

    二、堆排序

    现在做排序算法

    给一个数组，通过堆的排序算法把他们变成堆。原始的数组无序，也就是下面这样。

    1.     int arr[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
    2.     HeapSort(arr, sizeof(arr) / sizeof(int));

    这样的话我们有两个方案，做向上调整或者向下调整。

    1.     for (int i = 1; i < n; i++)
    2.     {
    3.         AdjustUp(a, i);
    4.     }
    5.     for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    6.     {
    7.         AdjustDown(a, n, i);
    8.     }

    现在默认是大堆。

    向上调整的思路就是遍历数组看成一个个插入，插入第一个不做操作，第二个开始就进行比较，然后决定是否交换位置。所以这里就从下标为1的位置开始循环，不断地UP。

    向下调整的思路则是所有数据无序，不能直接进行向下调整。其实这个条件可以从pop函数里看出来，pop操作时，整体是大堆顺序，交换首尾元素，size--，这样整个堆里除了根节点，左子树和右子树都是大堆，这种情况向下调整可行。所以同样，这里就不能直接调整，但从尾开始调整是可以的。找到尾部元素的父节点，一一调整。

    但是一般使用向下调整。假设是一个完全二叉树，N为节点数，h是高度。向下调整的次数是2^h -1 -h，也就是N - h，也就是N - log2(N + 1)，最后时间复杂度就是O(N)。

    而向上调整最后一层的最大调整次数就是2^(h-1) * (h-1)，把它变成2^h*(h-1) / 2，也就是(N + 1)(log2N + 1) / 2,，所以仅最后一层都达到了N * log2N，所以向上调整的时间复杂度明显比向下大，而向上调整的时间复杂度就是O(N * log2N)。

    在二叉树里，最后一层的节点数最多，而向下调整跳过了最后一层，直接从最后一层的父节点开始调整，并且从下到上，节点数多的调整少，而向上调整则是节点多的调整多，最后一层更是很多调整。所以不管是不是全部都要调整，向下调整次数都明显比向上少。

    所以用向下调整法，向下调整的条件是根节点的左右子树都是堆。

    向下调整选好了，接下来思考另一个问题，如果要升序的话，应该是建立大堆还是小堆？假如现在建小堆，面对一串无序的数字，即使建成小堆，也有可能不是升序，因为第二层的两个数可以不按照小到大的顺序排。如果pop掉第一个元素，把它放到另一个空间里，然后一个个插入来调整做成小堆可以，但是这样空间复杂度变高了。但是不开辟空间的话，在原始数组里调整，会发现数字之间的关系很容易乱掉，耗掉了很多时间。所以升序还是建立大堆。

    大堆选好后，我们开始做升序。关于升序，我们可以把首尾元素互换一下，这样最大值出现在尾部，然后对于前面的数值，不包含数组中最后一个数值，进行向下调整找到次大值，次大值这时候在数组首部，再次调换，和倒数第二个数字调换，因为最后一个已经被排除在外了，不管它了，它也是比这个次大值更大的值，调换完后这个次大值排在倒数第二个位置，之后重复这个操作。

    1. void AdjustDown(HPDataType* a, int n, int parent)
    2. {
    3.     int child = parent * 2 + 1;
    4.     while (child < n)
    5.     {
    6.         //确认child指向大的那个孩子并且child要小于size
    7.         if (child + 1 < n && a[child + 1] > a[child])
    8.         {
    9.             ++child;
    10.         }
    11.         if (a[child] > a[parent])
    12.         {
    13.             Swap(&a[child], &a[parent]);
    14.             parent = child;
    15.             child = parent * 2 + 1;
    16.         }
    17.         else
    18.         {
    19.             break;
    20.         }
    21.     }
    22. }
    23.  
    24. void HeapSort(HPDataType* a, HPDataType n)//O(N * logN)
    25. {
    26.     //0(N)
    27.     for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    28.     {
    29.         AdjustDown(a, n, i);
    30.     }
    31.     int end = n - 1;
    32.     //O(N * logN)
    33.     while (end > 0)
    34.     {
    35.         Swap(&a[0], &a[end]);
    36.         AdjustDown(a, end, 0);
    37.         end--;
    38.     }
    39. }

    当然如果向下调整里a[child + 1] > a[child]以及a[child] > a[parent]改成<，那么就是降序了。

    1. void TestHeap4()
    2. {
    3.     int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
    4.     HeapSort(array, sizeof(array) / sizeof(int));
    5.  
    6.     for (int i = 0; i < sizeof(array) / sizeof(int); ++i)
    7.     {
    8.         printf("%d ", array[i]);
    9.     }
    10.     printf("\n");
    11. }

    三、TOPK问题

    接着来下一个问题。

    在一些数据中找到十个最大的数据，把这个数字设为k，也就是找到前k个大的数据。当然我们可以一个个比较，但是正因为数据量不确定，所以情况不能这样简单。假设是有N个数字，N为十亿，百亿个，如果还是之前的办法是肯定不可行的。我们现在用堆来解决。堆如何找到最大的那k个数字？如果建立一个大堆，放进所有数字，那么最大的那几个一定是在前面的，这样取堆顶，然后pop掉（pop里面有向下调整），再取堆顶，就能找到前十个了。虽然这个思路可以，但是忘了一个重要的事，还是数据很大的问题。百亿个数字，建立一个百亿数字的大堆，这需要占用多少内存？算下来，几十G。所以，这个方法其实是不现实的。单论这个思路来讲，时间复杂度是N + logN * K，空间复杂度是O(1)。

    现在换另一个思路，假设k就是10吧，前10个大的数字集合起来叫做O，用整个数据集里前10个数字作一个小堆，这个小堆都有哪些数字不需要担心，即使有O里面的数字也可，因为它一定大于其它所有的数字，也一定在堆里面靠下点的位置。之后遍历剩下的数字，每个都和现有小堆的堆顶比较，小于就无操作，大于就进堆，如果遇到O里面的数字，假设编号是O1 - O10，无论哪个数字，都一定会进堆，然后放在下面。假如遍历到最后时，才遇到O1或者O10也没有关系，遇到O1会进堆，此时其他数字都进来了，那么排在第一层的就相对来说是一个小数字，进入后不断向下调整，堆顶就会变为O10，最后整个堆就是O里的数字。O10也一样，一定会替换掉堆顶，自己做堆顶。其他哪一个O里的数字都一样。

    而这样的时间复杂度是K + (N - K) * logK，空间复杂度为K。这种做法会直接在磁盘里读取数据，空间问题也就解决了。

    接下来是代码展示。

    先随机1000个数字，范围在10000之内

    1. int main()
    2. {
    3.     //TestHeap2();
    4.     //TestHeap3();
    5.     //TestHeap4();
    6.     srand(time(NULL));
    7.     int j = 0, i = 0;
    8.     FILE* fd = fopen("E:\\C++File\\data.txt", "a");
    9.     if (fd == NULL)
    10.     {
    11.         perror("fopen fail");
    12.         return;
    13.     }
    14.     for (i = 0; i < 1000; ++i)
    15.     {
    16.         j = rand() % 1000;
    17.         fprintf(fd, "%d\n", j);
    18.     }
    19.     fclose(fd);
    20.     TestHeap5();
    21.     return 0;
    22. }

    向下调整改成小堆。

    1. //如果a[child + 1] < a[child]  a[child] < a[parent]，那么就是降序了。
    2. void AdjustDown(HPDataType* a, int n, int parent)
    3. {
    4.     int child = parent * 2 + 1;
    5.     while (child < n)
    6.     {
    7.         //确认child指向大的那个孩子并且child要小于size
    8.         if (child + 1 < n && a[child + 1] < a[child])
    9.         {
    10.             ++child;
    11.         }
    12.         if (a[child] < a[parent])
    13.         {
    14.             Swap(&a[child], &a[parent]);
    15.             parent = child;
    16.             child = parent * 2 + 1;
    17.         }
    18.         else
    19.         {
    20.             break;
    21.         }
    22.     }
    23. }

    测试函数

    1. void TestHeap5()
    2. {
    3.     int minHeap[10];
    4.     int k = 10;
    5.     int n = 1000;
    6.     int m = 0;
    7.     FILE* ft = fopen("E:\\C++File\\data.txt", "r");
    8.     if (ft == NULL)
    9.     {
    10.         perror("fopen fail");
    11.         return;
    12.     }
    13.     for (int i = 0; i < k; ++i)
    14.     {
    15.         fscanf(ft, "%d", &minHeap[i]);
    16.     }
    17.     for (int i = (k - 1 - 1) / 2; i >= 0; --i)
    18.     {
    19.         AdjustDown(minHeap, k, i);
    20.     }
    21.     while (fscanf(ft, "%d", &m) != EOF)
    22.     {
    23.         if (m > minHeap[0])
    24.         {
    25.             minHeap[0] = m;
    26.             AdjustDown(minHeap, k, 0);
    27.         }
    28.     }
    29.     for (int i = 0; i < k; ++i)
    30.     {
    31.         printf("%-7d", minHeap[i]);
    32.     }
    33.     printf("\n");
    34.     fclose(ft);
    35. }

    这里数组也可以malloc。

    但是这还有一个问题，程序给出的结果就真的是最大的那10个吗？我们应该怎么判定？其实我们可以主动对数据做点动作，改变k个数据，让他们变成毫无疑问的最大，并且也可以通过%上一个值来确定好它们的位置，比如我这里% 47 == 0，也就是只在47的倍数处是超大值，这里就随便写。这里我把生成随机数也放进测试函数里。

    1. void TestHeap5()
    2. {
    3.     // 造数据
    4.     int n = 1000;
    5.     int k = 10;
    6.     srand(time(0));
    7.     FILE* fin = fopen("data.txt", "w");//不用a的原因是a是追加，如果多次运行起来，这个文件会越来越大，执行时间会更慢，所以用w每次都清空再写入1000个
    8.     if (fin == NULL)
    9.     {
    10.         perror("fopen fail");
    11.         return;
    12.     }
    13.  
    14.     int randK = k, j = 0;
    15.     for (size_t i = 0; i < n; ++i)
    16.     {
    17.         j = rand() % 1000;
    18.         if (randK && (i % 47 == 0))
    19.         {
    20.             j = randK + 10000;
    21.             --randK;
    22.         }
    23.         fprintf(fin, "%d\n", j);
    24.     }
    25.  
    26.     fclose(fin);
    27.  
    28.     /
    29.     //建立TOP K数组
    30.     FILE* fout = fopen("data.txt", "r");
    31.     if (fout == NULL)
    32.     {
    33.         perror("fopen fail");
    34.         return;
    35.     }
    36.  
    37.     int* minHeap = (int*)malloc(sizeof(int) * k);
    38.     if (minHeap == NULL)
    39.     {
    40.         perror("malloc fail");
    41.         return;
    42.     }
    43.  
    44.     for (int i = 0; i < k; ++i)
    45.     {
    46.         fscanf(fout, "%d", &minHeap[i]);
    47.     }
    48.  
    49.     // 建小堆
    50.     for (int i = (k - 1 - 1) / 2; i >= 0; --i)
    51.     {
    52.         AdjustDown(minHeap, k, i);
    53.     }
    54.  
    55.     //找TOP K
    56.     int val = 0;
    57.     while (fscanf(fout, "%d", &val) != EOF)
    58.     {
    59.         if (val > minHeap[0])
    60.         {
    61.             minHeap[0] = val;
    62.             AdjustDown(minHeap, k, 0);
    63.         }
    64.     }
    65.  
    66.     for (int i = 0; i < k; ++i)
    67.     {
    68.         printf("%d ", minHeap[i]);
    69.     }
    70.     printf("\n");
    71.     fclose(fout);
    72. }
    73.  
    74. int main()
    75. {
    76.     //TestHeap2();
    77.     //TestHeap3();
    78.     //TestHeap4();
    79.     TestHeap5();
    80.     return 0;
    81. }

     结果不会是顺序的1001-1010，会打乱顺序，但值确实是最大的10个。建议用Release模式，更快。

    结束。下一篇开始写链式二叉树。

  • 相关阅读:
    滚动更新和回滚部署在 Kubernetes 中的工作原理
    OpenSSL 编程 一：基本概念
    网络安全：windows批处理写病毒的一些基本命令.
    Java纯注解开发模式
    【数据结构练习题】消失的数字 --- 三种解法超详解
    瑞吉外卖 新增员工功能
    设计模式-行为型-中介者模式
    Python制作自动填写脚本，100%准确率
    技能大赛训练题：ftp 服务攻防与加固
    Mysql的JDBC增删改查
  • 原文地址：https://blog.csdn.net/kongqizyd146/article/details/127999082