堆以及堆的相关应用 |
您所在的位置：网站首页 › 二叉堆插入时间复杂度 › 堆以及堆的相关应用 |
堆以及堆的相关应用
|
前言
本文先会介绍堆这种数据结构的特点和常见操作函数，然后详细讲解利用堆的特点来实现堆排序，最后会介绍堆的另一个应用——TopK问题。 对于想要学习堆或者巩固相关知识的同学，看完本文一定会对你有所帮助。 一.什么是堆？堆是一种数据结构，更具体地说，堆是一种特殊的二叉树。它的特殊之处在哪呢？ 第一，它是一棵完全二叉树，并以顺序存储的方式存储在一个一维数组中。 第二，对于每一个结点点，它必须大于等于它的孩子，或者小于等于它的 孩子。因此，堆可以分为大根堆和小根堆，大根堆是前者而小根堆属于后者。 第三，根据第二个特点，我们可以知道在一个堆中，根结点就是最大值或者是最小值，这一点我们在堆排序以及 topk问题中都有重要的应用 下面我们来介绍堆的一些基本操作 结构表示我们用一个结构体来封装堆的所有信息。其中包括一个一维数组指针，数组的容量以及数组的大小。 typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; 初始化操作 void HeapInit(HP* php) { assert(php); //初始化给四个空间 php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4); if (php->a == NULL) { perror("malloc fail!\n"); exit(-1); } php->capacity = 4; php->size = 0; } 插入操作插入是在已经有一个堆的前提下，这里我们假设已经有了一个堆。 我们将要插入的元素放到堆的尾部，然后再通过调整将它放在合适的位置，那么，怎么调整呢？ 我们以大根堆为例，后续也都是以大根堆为例。将这个节点与它的父节点做比较，如果说它比父节点的值要大，这样就违背了大根堆的特点，那么，就将它和父结点交换。然后继续将它和新的父结点相比，进行相同的操作，直到它小于等于父节点，或者成为了根节点。这样，他就到达了合适的位置，跳出循环即可。这个过程我们将它称为向上调整 。 void AdjustUp(HPDataType* a, int child) { //大根堆--父亲必须大于等于孩子，如果孩子大于父亲就要调整 assert(a); int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { Swap(&a[parent], &a[child]); } else { break; } child = parent; parent = (child - 1) / 2; } }插入操作如下： void HeapPush(HP* php, HPDataType x)//在已经有堆的基础上 { assert(php); //检查容量 if (php->size == php->capacity) { int newCapacity = php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); if (tmp == NULL) { perror("realloc fail\n"); exit(-1); } php->a = tmp; php->capacity = newCapacity; } //放到堆尾 php->a[php->size] = x; php->size++; //向上调整 AdjustUp(php->a, php->size - 1); } 建堆对于一个空的数组，我们也可以将它看成是一个堆。那么，我们就可以将数据一个一个插入从而建堆。 int arr[] = { 1,2,3,4,5,6,7,8 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { HeapPush(&hp, arr[i]); } 删除堆顶元素怎么删除呢？这太不简单？将所有的元素向前挪动一位覆盖第一个元素不久行了吗？ 没有想的那么简单，因为你现在不是对一个普通的顺序表进行操作，如果你这么做，再将这个数组还原成完全二叉树，那么原先的父子关系完全错乱了。兄弟变父亲，父亲变兄弟，完全乱套了。 真正的办法是替换法删除：先将根结点与末尾的末尾的结点交换。然后放心地将尾节点删除。接着将根结点“向下调整”。向下调整法和向上调整法类似，都是通过将孩子和父亲不断比较，然后的交换位置从而建成一个新堆，这里同样以大根堆为例 void AdjustDown(int* a, int n, int parent) { //大根堆--父亲必须大于等于孩子，否则交换 int child = 2 * parent + 1; while (child a[parent]) { Swap(&a[child], &a[parent]); } else { break; } parent = child; child = 2 * parent + 1; } } void HeapPop(HP* php) { //将堆头元素和堆尾元素交换后，堆头元素向下调整到合适位置 assert(php); assert(!HeapEmpty(php)); Swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); }还有一些基本操作，例如判断堆是否为空，堆的大小，取堆顶元素等，这些就不赘述了。 二.堆排序堆排序是堆这种数据结构的重要应用，这种排序方法的时间效率非常高，可以达到O(logn),和快排是一个级别的。说明一点，我们在堆排序时，一般都是给定一个数组，然后让你对它进行排序，这时我们没有必要像上面那样还封装一个结构体来记录数组的容量和大小，而是直接在这个数组上面做文章。 如何建堆？堆排序的第一步是建一个堆，如何建堆？上面我们时从一个空数组开始，依次插入元素，也就是向上调整，最终从无到有建立了一个堆。而这里一开始就有了一个非空数组又该怎么办呢？其实很简单。 我们知道，向上调整的基础是在堆已经建好的基础上，当数组是空的，可以看成是一个堆。当数组只有一个元素时，照样是一个堆(根节点大于等于孩子)。所以我们可以从第二个元素开始，将后面的元素都用手“蒙住”，然后依次向上调整。这里的“蒙住”怎么操作呢？ void AdjustUp(HPDataType* a, int child) 看上面的这个声明，你只需要将数组传给a, 将要调整的元素的下标传给child, 那么这个函数就会从child这个位置开始向上调整，而你child位置的后面有没有元素我根本不关心。所以整体的步骤和以前的建堆方式差不多。 //向上调整建堆 int arr[] = {1,2,3,4,5,6,7,8}; int size = sizeof(arr) / sizeof(arr[0]); for (int i = 1; i < size; i++)//从第二个结点开始调整 { Adjustup(arr, i); }下面介绍另一种建堆方式，向下调整建堆，这种方法才是常用的，因为它的时间效率更高。 向下调整建堆的基础也是在堆已经建好的基础上，所以我们从哪个位置开始调整呢？答案是尾结点的父节点。 //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从倒数第一个非叶子结点开始调整 { AdjustDown(a, n, i); } 两种建堆方式的时间复杂度比较向上调整建堆
向下调整建堆
显然向下调整建堆方法优于向上调整建堆 排序过程还记得堆的第三条性质吗，对于一个大堆，堆顶的数是这些数中最大的。 假如我想排升序，那么我就先建一个大堆，将堆顶元素与堆尾元素交换位置，这样数组最后一个位置就放上了最大的数，这个位置不能动了，所以将它排除在堆的外面。 然后我再通过把堆顶的元素向下调整得到一个新堆，接下来步骤和上面一样（注意这里的堆尾不是数组的末尾，因为在排序的过程中堆会不断缩小） 如此循环往复，直到堆中只剩下一个元素时，堆排序也就完成了，所有元素放在了正确的位置。 整个堆排序的完整代码如下 void HeapSort(int* a, int n) { assert(a); //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从倒数第一个非叶子结点开始调整 { AdjustDown(a, n, i); } //每次取堆顶元素放在后面的指定位置，让后向下调整得到一个新堆 int end = n - 1; while (end > 0) { Swap(&a[end], &a[0]); AdjustDown(a, end, 0); end--; } }总结一下，堆排序首先要通过向下调整的方式建堆，然后取堆顶元素放到末尾，堆的大小减去1。然后向下调整得到新堆，重复以上步骤。堆的大小在这个过程中会不断缩小，直到堆中只有一个元素时，堆排序圆满结束。 那么这个排序过程的时间复杂度是多少呢？这里的时间消耗其实是每次的调整建堆过程，每当我排完一个数，我就要将堆顶元素向下调整到该数的层次。其实这个过程可以看成是向上调整建堆的逆过程，上面已经算过，时间复杂度是O(N*logN)。所以整个堆排序的时间复杂度就是O(N+NlonN)，也就是O(NlogN)。 三.TopK问题TopK问题就是在若干个数中选出最大的或最小的K个数，比如在某购物平台选出销量前10的商品。 有人说这还不简单，前面不是学了堆排序吗？我直接来一手堆排降序，然后前10个元素即为所求。堆排的效率确实很高，达到了O(N*lonN),但是再快也经不住你这么造啊，假如我有上亿件商品呢？我就为了得到10件商品就把它们全排一遍，太浪费了吧。 于是提出解决方案，那我只排十个数可以吧，前面说过，每建一次堆可以排一个数，那么我建10次就OK了。这样的话时间问题倒是解决了，但是空间呢？你有一亿个数，堆区都存储不下，更不要说栈区了。 下面介绍正确的方法： 先从这一亿个数中拿十个数来建一个小堆(为什么是小堆后面分析)，然后每次从剩下的数中拿一个数和堆顶元素比较，如果比堆顶的元素大，就用它把堆顶的数替换掉，然后向下调整得到一个新堆。重复此过程，直到将这一亿个数全部取完，得到的十个数的堆即为所求。 为什么要建小堆呢？因为小堆的堆顶元素是最小的，如果一个数比堆顶元素小，那么它最少能排前10。相反，如果你建一个大堆，假如一开始堆顶元素就是一亿个数中最大的那个，那么完蛋了，接下来所有数都被这个门神死死地挡在门口进不了堆。 void CreateData() { //1.打开文件 FILE* pfile = fopen("data.txt", "w"); if (pfile == NULL) { perror("fopen fail"); fclose(pfile); return; } //2.写数据 int n = 1000000; srand((unsigned int)time(NULL)); //随机产生数字 while (n--) { fprintf(pfile, "%d\n", rand()); } //3.关闭文件 fclose(pfile); } void PrintTopK(int k) { //先从文件中读k个数 //1.打开文件 FILE* fin = fopen("data.txt", "r"); //2.读取文件 int* kminheap = (int*)malloc(sizeof(int) * k); if (kminheap == NULL) { perror("malloc fail"); return; } for (int i = 0; i < k; i++) { fscanf(fin, "%d", &kminheap[i]); } //建小堆（大的数沉到下面） for (int i = (k - 1 - 1) / 2; i > 0; i--) { AdjustDown(kminheap, k, i); } //依次从文件中读取数据，插入到堆中 int val = 0; while (fscanf(fin, "%d", &val) != EOF) { if (val > kminheap[0]) { kminheap[0] = val; AdjustDown(kminheap, k, 0); } } if (ferror(fin)) { perror("fscanf fail"); fclose(fin); return; } //3.关闭文件 fclose(fin); //输出堆 for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } } int main() { CreateData(); PrintTopK(10); return 0; }先随机产生若干个数存储在文件里，然后不断地从文件中读取数据，处理数据。 总结：对于堆的相关知识，重点要掌握堆排序的过程，学会如何向下调整法建堆，分析堆排序的时间复杂度等 如果分享的内容对你有所帮助，记得点赞收藏，有任何问题欢迎评论区下方留言。 |
【本文地址】
今日新闻 |
推荐新闻 |