数据结构（堆）
一.概念及其介绍
1.堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于等于儿子结点存储数据（也可以是父亲结点数据都要小于等于儿子结点数据）的一种数据结构。
堆只有两种即大堆和小堆，大堆就是父亲结点数据大于等于儿子结点数据，小堆则反之。
2.堆满足下列性质：
堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是一棵完全二叉树。
二.适用说明
堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。
若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2)，堆这种数据结构也可以提高入队和出队的效率。
三.堆结构
二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。
其中堆的根节点最大称为最大堆，如下图所示：
四.堆的应用
优先队列实现：用于操作系统任务调度、图算法（如 Dijkstra 算法）等，根据元素优先级处理元素。
堆排序：对数组元素排序，时间复杂度 O (n log n)。
求第 K 大（小）元素：可快速找出第 K 大或第 K 小元素。
中位数维护：使用两个堆维护数据流的中位数。
合并 K 个有序列表：高效合并多个有序列表为一个有序列表。
原文地址：https://blog.csdn.net/xieliru/article/details/145191073
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！