数据结构之堆详解
1. 概述
堆（也叫优先队列），是一棵完全二叉树，它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。
2. 堆的基本操作
堆是一棵完全二叉树，高度为O（lg n），其基本操作至多与树的高度成正比。在介绍堆的基本操作之前，先介绍几个基本术语：
A：用于表示堆的数组，下标从1开始，一直到n
PARENT(t)：节点t的父节点，即floor(t/2)
RIGHT(t)：节点t的左孩子节点，即:2*t
LEFT(t)：节点t的右孩子节点，即:2*t+1
HEAP_SIZE(A)：堆A当前的元素数目
下面给出其主要的四个操作（以大顶堆为例）：
2.1 Heapify(A,n,t)
该操作主要用于维持堆的基本性质。假定以RIGHT(t)和LEFT(t)为根的子树都已经是堆，然后调整以t为根的子树，使之成为堆。
void Heapify(int A[], int n, int t)
{
int left = LEFT(t);
int right = RIGHT(t);
int max = t;
if(left <= n) max = A[left] > A[max] ? left : max;
if(right <= n) max = A[right] > A[max] ? right : max;
if(max != A[t])
{
swap(A, max, t);
Heapify(A, n, max);
}
}
2.2 BuildHeap(A,n)
该操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。
void BuildHeap(int A[], int n)
{
int i;
for(i = n/2; i<=n; i++)
Heapify(A, n, i);
}
2.3 GetMaximum(A,n)
该操作主要是获取堆中最大的元素，同时保持堆的基本性质。堆的最大元素即为第一个元素，将其保存下来，同时将最后一个元素放到A[1]位置，之后从上往下调整A，使之成为一个堆。
void GetMaximum(int A[], int n)
{
int max = A[1];
A[1] = A[n];
n--;
Heapify(A, n, 1);
return max;
}
2.4 Insert(A, n, t)
向堆中添加一个元素t，同时保持堆的性质。算法思想是，将t放到A的最后，然后从该元素开始，自下向上调整，直至A成为一个大顶堆。
void Insert(int A[], int n, int t)
{
n++;
A[n] = t;
int p = n;
while(p >1 && A[PARENT(p)] < t)
{
A[p] = A[PARENT(p)];
p = PARENT(p);
}
A[p] = t;
return max;
}
3. 堆的应用
3.1 堆排序
堆的最常见应用是堆排序，时间复杂度为O(N lg N)。如果是从小到大排序，用大顶堆；从大到小排序，用小顶堆。
3.2 在O(n lg k)时间内，将k个排序表合并成一个排序表，n为所有有序表中元素个数。
【解析】取前100 万个整数，构造成了一棵数组方式存储的具有小顶堆，然后接着依次取下一个整数，如果它大于最小元素亦即堆顶元素，则将其赋予堆顶元素，然后用Heapify调整整个堆，如此下去，则最后留在堆中的100万个整数即为所求 100万个数字。该方法可大大节约内存。
3.3 一个文件中包含了1亿个随机整数，如何快速的找到最大(小)的100万个数字?（时间复杂度：O（n lg k））
4. 总结
堆是一种非常基础但很实用的数据结构，很多复杂算法或者数据结构的基础就是堆，因而，了解和掌握堆这种数据结构显得尤为重要。
5. 参考资料
（1）经典算法教程《算法导论》
相关文章
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了解决jmap命令打印JVM堆信息异常的问题，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-04
- 这篇文章主要介绍了C#常用数据结构和算法，这里我们总结了一些知识点，可以帮助大家理解这些概念。...2020-06-25
- 本文主要和大家分享几种Redis数据结构详解，希望文中的案例和代码，能帮助到大家。...2021-01-15
- 这篇文章主要为大家详细的介绍了Redis高效的原因以及分析了Redis高效的数据结构，有需要的朋友可以借鉴参考下，希望能够有所帮助...2021-09-27
- 上文对数据结构与算法，有了一个简单的概述与介绍，这篇文章，我们介绍一中典型数据结构——线性结构...2020-06-25
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家，让大家理解掌握这部分内容，需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++数据结构与算法之哈夫曼树的实现方法,简单说明了哈夫曼树的原理,并结合具体实例形式分析了C++实现哈夫曼树的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了基于JavaScript的数据结构队列动画实现示例解析，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-08-06
- 这篇文章主要介绍了数据结构 双向链表的创建和读取详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
C语言之栈和堆（Stack && Heap）的优缺点及其使用区别
本篇文章主要介绍了什么是栈（Stack） 、什么是堆（ Heap），以及栈和堆的优缺点，同时介绍了应该什么时候使用堆和栈,有需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言数据结构之动态分配实现串的相关资料,希望通过本文能帮助到大家，让大家实现数据结构中动态分配实现串的实例，需要的朋友可以参考下...2020-04-25
- <? //-------------------- // 基本数据结构算法 //-------------------- //二分查找（数组里查找某个元素） function bin_sch($array, $low, $high, $k){...2016-11-25
- 我们在进行编程时，往往会开发诸多的算法，那么我们怎么在那么多算法中找到最好的那个呢？本文主要介绍时间和空间复杂度概念及时间复杂度的求解，预祝读者学习愉快...2021-10-23
- 这篇文章主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构树的双亲表示法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中数据结构之链式基数排序的相关资料,希望通过本文能帮助到大家，需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#托管堆对象实例包含内容,实例展示了托管对象的结构及运行原理,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C语言数据结构之使用链表模拟栈的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了数据结构之树的概念详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-09-10