点击上方蓝字MintyMentors关注我们
遇见你专属的行业导师 开启求职新鲜旅程
实习，全职，全球职位招聘尽在明途求职
你可能还不够了解的 数据结构
Heap堆
初学数据结构的时候我们可能都觉得它很枯燥，既看不懂它是咋实现的，也不知道它究竟有啥用，就知道这个面试要考，所以我要会。其实，随着我们编码年龄的增长，我们就会越来越觉得数据结构真的是可堪大用，能熟练应用数据结构也是一个计算机工程师能力的试金石，这也解释了它为什么在任何级别的工程师面试中都未曾缺席过。
之所以选择了它是因为在很多初学的小伙伴眼里，它好像很神秘很复杂的样子，但其实他并不比我们熟知的二叉树、单链表更加高贵，今天我们就来一起揭开它的面纱。有信心的小伙伴可以看看能答对多少题~
以下关于堆（Heap）的描述哪个是对的？
一定是二叉树的一种
一种特别的树状结构
单链表的一种
A和B都对
▼点击空白区域查看答案

它是计算机科学中的一种特别的树状结构
我们常用的堆是二叉堆（binary heap）也就是基于二叉树结构实现的堆，但是请注意，堆不是一定是二叉树哦，所以我们只是常用“堆”来代指“二叉堆”，在这里我们也会继续沿用这一种叫法。堆是一种特殊的二叉树，它必须是完全二叉树（complete tree），也就是说如果你将一颗二叉树按照从上到下从左到右的顺序依次从1开始编号，编号序列是连续自然数而中间没有空缺。
最小堆的特点是
同层节点之间没有必然的大小关系
父节点一定比自己的叶子节点小
根节点一定是最小的或之一
以上都对
▼点击空白区域查看答案

Heap基本可以分为最大堆（max heap）和最小堆（min heap）两种
请注意任意结点P和C，若P是C的父结点，则P的值一定小于等于C的值
 重要结论：
1. 根节点的值一定是最小的（或之一）
2. 父结点的值必然小于等于它的任何一个子结点
3. 同层节点之间没有必然的大小关系
如何插入一个节点？
最底层的最右边
最顶层
位置都可以，因为最终会上浮
最底层
▼点击空白区域查看答案

由于需要维持完全二叉树的结构，我们需要先将新节点插入最底层的最右边，然后逐层与它的父节点比较，如果它的值比父节点的值小（最小堆为例），交换两个节点，也叫“节点上浮”。
所以我们可以观察到，最坏的情况是我们插入了一个最小的点，然后将它一路“上浮”到跟节点，走过的路径就是二叉树的高度，如果我们用N代表节点总数，它的时间复杂度就是O(logN)。
堆的最好实现方式是？
heapq
数组
java的heap结构
Quene
▼点击空白区域查看答案

用JAVA的同学应该知道，在JAVA中并没有叫heap的结构，而是使用PriorityQueue实现了heap。同样的在python中对应的module叫做heapq。那么这是不是意味着heap其实是通过queue实现的呢？答案是可以，但不是最好。我们知道越底层越基础的数据结构的使用开销是越小的，所以heap在很多语言里都是用数组实现的，而且不要觉得这是一项多么难的工程，我们经过简单的学习也能轻而易举地用array实现自己的heap结构。
以下哪个选项是初始化一个堆结构的最优时间复杂度？
o(NlogN)
o（n）
o（n^2）
N(LogN)
▼点击空白区域查看答案

既然我们可以用数组实现堆结构，那么我们最初是怎么把一个数组初始化成一个堆结构的呢？聪明的小伙伴可能已经想到了，很简单，把每个元素以此插入这个堆不就行了么？当然，这个方法叫做“插入法”，假设我们一共有N个元素，每次插入的时间复杂度是logN, 所以初始化这个堆的总时间复杂度就是O(NlogN)。但是你知道这并不是最好的方法吗？其实我们可以用平均O(N)的时间进行高效的heapify操作。
以下关于堆（Heap）和栈（stack）的哪个描述是对的？
堆：时效临时、局部可见、手动申请、手动释放
栈：时效持久、全局可见、自动申请、自动释放
堆：时效持久、局部可见、自动申请、自动释放
栈：时效临时、全局可见、手动申请、手动释放
堆：时效临时、全局可见、手动申请、自动释放
栈：时效持久、局部可见、自动申请、自动释放
堆：时效持久、全局可见、手动申请、手动释放
栈：时效临时、局部可见、自动申请、自动释放
▼点击空白区域查看答案

为什么我经常听到别人说“堆栈”？为什么堆（heap）和栈（stack）能相提并论呢？
其实这是一个专业用语的问题，堆（heap）和栈（stack）有两个含义，一个是指抽象数据结构，另一个则是指操作系统中的内存空间。前者它们实现和作用都有很大差异所以比较少被放在一起比较，而后者则是同气连枝常常被“相提并论”。堆在操作系统中为按需申请、动态分配，由于内存中的空闲空间不是连续的，操作系统会根据应用程序提出的申请从堆中按照一定的算法找出可用内存标记后给程序使用；而操作系统中的栈则是程序运行时自动拥有的一小块内存，大小由编译器参数决定，用于局存放局部变量或者函数调用栈的保存。它们的区别如果长篇大论会讲非常多的内容，简单总结起来就是：
· 堆：时效持久、全局可见、手动申请、手动释放
· 栈：时效临时、局部可见、自动申请、自动释放
其实Data Science没有
你想的那么复杂难懂，
欢迎加入Minty TECH刷题营
在导师们的生动讲解下，
和小伙伴一起轻松刷题拿offer！
👇👇👇
今日推荐
MintyMentors明途求职是隶属于北美留学生网。立足美国，服务全球的最专业的职业咨询平台。总部设于美国波士顿，在纽约、加州等地区设有分公司。我们联合来自麦肯锡、高盛、德勤、微软等十几个行业的职场精英，为北美留学生提供个性化的职业评估、一对一行业导师咨询、文书修改、模拟面试、职位内推等服务。我们独创 N+1 求职辅导模式，为每位学员配备一位专属求职咨询师及多个行业导师，全程跟踪辅导学生的求职过程，直至学员进入理想的企业。
微信公众号ID ：mintymentors
在看点这里
继续阅读
阅读原文
关键词
内存
节点
二叉
结构
二叉树