堆数据结构以及堆排序

2012-12-28 21:56:21   最后更新: 2019-10-08 17:03:16   访问数量:998




在程序设计中,堆是一种非常重要但并不是特别常用的一种数据结构

堆数据结构通常用在优先级队列等排序的场景中,由于其结构的特性,在寻找最大/最小值的算法场景中,使用堆数据结构可以有效降低程序的时间复杂度

本文我们就详细介绍一下堆数据结构,并在下一篇文章中讲述堆在算法中的应用

 

堆是一种完全二叉树,它分为大根堆与小根堆,对于大根堆,其任何节点均大于等于其左右子节点,小根堆则恰好与之相反

因此,小根堆的根节点为堆中所有数据的最小值,大根堆的根节点则是堆中所有数据的最大值

由于堆是完全二叉树,所以堆无需存储每个节点的左右孩子指针,只需要通过一个数组存储先序遍历的所有数据即可

对于索引为 i 的节点,其左孩子节点的索引为 2*i + 1,其右孩子节点的索引为 2*i + 2,其父节点为 (i-1)/2

 

如果我们要构建一个堆,那么,我们只需要按照堆元素的插入算法,向堆中顺次插入所有元素即可,那么,接下来我们就以大根堆为例,来介绍一下堆节点的插入算法

每当一个元素插入,直接将元素放入数组的最后位置,由于元素插入前,所有元素已经是符合堆结构要求的,因此只需要比较该插入元素是否破坏了堆结构的要求即可

也就是说,通过将该元素与其父节点元素值进行比较,如果该元素的值大于其父节点,则将该节点与其父节点的值进行交换,接下来,再比较该元素的值与交换后父节点值的大小,递归上述过程即可

下图展示了这一过程,向一个大根堆插入了元素 16:

 

 

显然,新元素 16 的插入破坏了堆结构,因此需要进行值的交换操作:

 

 

交换后递归上述过程,仍然不满足对结构,因此需要进一步交换:

 

 

时间复杂度

可以证明,最差情况下,元素插入的过程需要遍历从根节点到叶子节点的单个分支,因此其时间复杂度为 O(logn)

因此,对于建堆过程而言,时间复杂度为 O(nlogn)

 

由于堆独特的数据结构特性,堆的根节点为堆中所有数据的最大值或最小值,因此我们通常只需要堆的根节点,或通过不断删除堆的根节点来实现整个数据集合的排序,这就是堆排序

那么,我们如何进行堆中元素的删除操作呢?

由于我们使用数组来进行堆的存储,所以只需要用数组末尾元素填充到数组首部,并且将数组元素数减 1,就可以实现根节点即数组首元素的删除,然后由于此步骤很可能会造成堆结构的破坏,我们需要进行调整从而保证堆结构的正确性

调整过程与新元素插入的过程非常类似,但是反向从上而下的,下列图片展示了这个过程:

 

 

 

 

 

时间复杂度

和堆中元素插入算法的时间复杂度一样,堆中元素删除算法的时间复杂度也是 O(logn)

 

上面我们已经讲到了堆排序,事实上,堆排序正是上述堆元素插入、建堆与堆元素删除过程的结合

因此,此处不再赘述算法细节,直接贴出代码:

 

main.c

/* * file: main.c * author: 龙泉居士 * date: 2012-12-28 21:55 */ #include <stdio.h> #include "function/function.h" int heap_sort (int *array, int n) { if (array == NULL || n<=0) { printf ("build_heap param error"); return -1; } else if (n == 1) return 0; build_heap (array, n); int i; for (i=n-1; i>0; --i) { exch (array, 0, i); con_heap (array, 0, i); } return 0; } int main () { int i, n=0; int array[256]; printf ("Please input numbers, end by 9999:\n"); while (1) { scanf ("%d", &array[n]); if (array[n] == 9999) break; ++n; } if (heap_sort(array, n)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

 

function.h

/* * file: function.h * author: 龙泉居士 * date: 2012-12-28 21:56 */ #ifndef FUNCTION_H_20121228 #define FUNCTION_H_20121228 int heap_sort (int *array, int n); int con_heap (int *array, int pos, int n); int build_heap (int *array, int n); int exch (int *array, int a, int b); #endif

 

 

function.c

/* * file: function.c * author: 龙泉居士 * date: 2012-12-28 21:56 */ #include <stdio.h> #include "function.h" int con_heap (int *array, int pos, int n) { if (array == NULL || n<=0) { printf ("con_heap param error"); return -1; } else if (n == 1) return 0; int i=pos; while (i<=n/2-1) { int tmp; if (i*2+2 < n) tmp = array[i*2+1]>array[i*2+2] ? i*2+1 : i*2+2; else tmp = i*2+1; if (array[i]>=array[tmp] || i*2+1 >= n) break; exch(array, i, tmp); i = tmp; } return 0; } int build_heap (int *array, int n) { if (array == NULL || n<=0) { printf ("build_heap param error"); return -1; } else if (n == 1) return 0; int i; for (i=n/2-1; i>=0; --i) if (con_heap (array, i, n)) return -1; return 0; } int exch (int *array, int a, int b) { if (array[a] == array[b]) { return 0; } if (array == NULL) { printf ("build_heap param error"); return -1; } array[a] = array[a]^array[b]; array[b] = array[a]^array[b]; array[a] = array[a]^array[b]; return 0; }

 

 

算法说明 -- 为什么不用小根堆

为什么要使用大根堆而不是小根堆呢?

事实上,小根堆也是可以完成这个任务的,对于 n 个元素的数组 array 来说,如果选用小根堆,则第 i 次循环是排序 i 到 n 的自数列,需要传递参数 i,而如果使用大根堆,则每次都将最大元素放到最后,只需传递数组个数 n 即可,子序列即 0 到 n

基于大根堆的算法和基于小根堆的算法是完全相同的,只是判断是否成堆的条件不同

 

时间复杂度

如上文所述,堆排序时间复杂度为 O(nlogn),空间复杂度为 O(1)

 

 

欢迎关注微信公众号,以技术为主,涉及历史、人文等多领域的学习与感悟,每周三到七篇推文,只有全部原创,只有干货没有鸡汤

 

 

算法导论

 






读书笔记      技术帖      算法      算法导论            heap      数据结构      龙潭书斋      排序      heapsort      堆排序      交换     


京ICP备15018585号