关键词：
文章目录
文章内容介绍大纲
一、二叉树的顺序存储
1.堆的存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示。
2.下标关系
已知 双亲 (parent) 的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
二、堆(heap)
1.概念
1.堆逻辑上是一棵完全二叉树
2.堆物理上是保存在数组中
3.满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
4.反之，则是小堆，或者小根堆，或者最小堆
5.堆的基本作用是，快速找集合中的最值
2.大/小 根堆
2.1小根堆
每棵树的根节点都是小于孩子节点，此时这棵树就叫做小根堆
2.2大根堆
每棵树的根节点都是大于孩子节点的，此时这棵树就叫做大根堆
我们在说 大小根堆 时，只说了 根节点比孩子节点大，没有说 左右孩子节点谁比谁大、谁比谁小.
所以得出结论
不管是 大根堆、还是小根堆，左右孩子的大小关系是不确定的，我们只能确定根节点和孩子节点的关系.
3.建堆操作
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。
根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
将一个二叉树 调整为一个 大根堆
这棵二叉树调整为 大根堆 必须将 每颗子树都调整为大根堆.
3.1向下调整
思想 步骤：
parent —> 根节点下标
child —> 孩子节点下标
1.从最后一棵子树进行调整.
2.每颗子树从根节点向下调整，如果左右孩子节点的最大值比这个根节点大，那么值互换，然后 parent 指向 child ,child = 2* parent + 1， 继续向下调整，直到 下标child 超出二叉树 范围.
3.重复第二步的操作，遍历每一颗子树，直到所有子树全部遍历完成.
代码实现：
我们对这个代码进行测试
测试堆中的结果：
时间复杂度分析：
粗略估算，可以认为是在循环中执行向下调整，为 O(n * log(n))（了解）实际上是 O(n)
堆排序中建堆过程时间复杂度O(n)怎么来的？
4.入队操作
步骤
1.判断是否满容
2.在数组的最后插入元素
3.调整为 大/小 根堆
在这几个步骤中，前两步我们都可以完成 ，第三步我们要注意：
利用 向上调整 调整为大/ 小根堆
之前我们介绍了 向下调整
这次我们说的是向上调整，与之前向上调整的思路十分相似~~
我们来说一下 向上调整的思路
4.1向上调整
4.2push 入队的完整代码展示
5.出队操作
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素与堆顶元素交换，然后通过向下调整方式重新调整成堆.
思路：
1.交换 数组首尾元素
2.usedSize- -,删除最后的元素
3.利用向下调整 ，调整为大/小 根堆
5.1pop 出队代码完全展示
6.查看堆顶元素
返回 下标为0的数组元素.返回堆顶元素.
现在我们来看一个 堆的 应用
7.TOK 问题
我们在这里 提出一个问题：
在一千万个数据中找到 前 10个最大的 数据,请问如何查找
我们有 几个想法
1.基本反应，给1000万个数据排序，取10个最大 的，我们直接 Arrays.sort () ;
这种排序方法当然也不是不可以，只不过时间复杂度非常大，在面试中写出这样的排序思路会落得下风.
2.将这1000个数据 建成一个大堆，每次将最大的取出，然后调整，取出10个即可.
这种方法的缺点则是， 堆太大了，我们建立的堆也会是 1000万，如果这个数据更大，那么堆也会更大，每次调整的复杂度也很大.
3.建立一个大小为 K 的小堆.
以上面这个数组为例，找出这组数据中的前三个最大的元素.
3.1 将当前数据的前三个 建立为小堆
3.2 遍历剩下的元素，依次和堆顶元素进行比较. 如果当前 i 下标元素 比堆顶元素大，就把i下标入队.
堆顶元素一定是最小的，每次都与堆顶元素进行比较，每次都将最小的那个剔除，最后遍历完，剩下的就是 最大的几个数据了嘛~
根据上面的这个 思路，我们同理可以解决很多类似的问题
7.1TOPK
找到一组数据中 最大的K个数据
建立 大小为 K 的小堆，依次遍历，最后堆中的数据 即为结果.
找到一组数据中 第K大的数据
建立 大小为 K 的小堆，依次遍历，最后堆顶元素 即为结果.
找到一组数据中 最小的K个数据
建立 大小为 K 的大堆，依次遍历，最后堆中的数据 即为结果.
找到一组数据中 第K小的数据
建立 大小为 K 的大堆，依次遍历，最后堆顶元素 即为结果.
8.堆排序
从小到大排序 —— 升序 建立大堆
从大到小排序 —— 降序 建立小堆
思路： 以升序 为 例
1.交换 数组 首尾 的元素，这样最大的堆顶元素 被放在数组的最后一个，此时 最后一个元素 已经定好序了.
2.此时从第一个到 倒数第二个再次调整，调整完后将堆顶元素 与倒数第二个元素交换，按照这样的逻辑规律，循环直到 有序.
我们以实际 例子说明…
1.首尾交换
2.向下调整
重复此操作直到全部有序
算法演示：
代码实现：
我们看一下排序的结果：
说明我们 堆排序成功运行~~
好了，堆的知识先讲到这里，希望大家多多练习~~
下节就是关于Java中堆的使用的知识及练习了，大家敬请期待~~
未完待续~~
java集合与数据结构——优先级队列（堆）
文章目录一、二叉树的顺序存储1.堆的存储方式2.下标关系二、堆(heap)1.概念2.大/小根堆2.1小根堆2.2大根堆3.建堆操作3.1向下调整4.入队操作4.1向上调整4.2push入队的完整代码展示5.出队操作5.1pop出队代码完全展示6.查看堆顶元素7.TOK... 查看详情
java集合与数据结构优先级队列堆(代码片段)
Java集合与数据结构优先级队列【堆】二叉树的顺序存储存储方式堆(heap)操作-向下调整堆的应用-优先级队列操作-入队列操作-出队列java中的优先级队列堆的其他应用TopK问题堆的其他应用堆排序二叉树的顺序存储存储方式使用数... 查看详情
java集合与数据结构——优先级队列的使用及练习
...头的重量未完待续…本文内容介绍大纲接上篇Java集合与数据结构——优先级队列（堆）一、对象比较的方法 上节课我们讲了优先级队列，优先级队列在插入元素时有个要求&#x 查看详情
java集合数据结构——优先级队列(堆priorityqueue)(代码片段)
文章目录一、二叉树的顺序存储1.存储方式2.父亲和孩子的下标关系二、堆(heap)1.堆的基本概念2.堆的操作(1)建堆（向下调整）(2)建堆的时间复杂度(3)入队（向上调整）(4)出队（向下调整）三、Java中的优先级... 查看详情
优先级队列（堆）(代码片段)
...的概念我们都知道队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时可能需要优先级高的元素出队列，此时队列就显得不合适了。因此我们引入优先级队... 查看详情
优先级队列（堆）(代码片段)
...的概念我们都知道队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时可能需要优先级高的元素出队列，此时队列就显得不合适了。因此我们引入优先级队... 查看详情
数据结构java数据结构----堆(优先级队列)(代码片段)
文章目录堆(优先级队列)1.二叉树的顺序存储1.1存储方式1.2下标的关系2.堆2.1概念3.模拟实现PriorityQueue①基本操作②向下调整③建堆④入队列⑤出队列⑥堆排序4.堆的应用-优先级队列4.1java中的优先级队列4.2java中堆的使用5.集合框... 查看详情
死磕java集合之priorityqueue源码分析
问题（1）什么是优先级队列？（2）怎么实现一个优先级队列？（3）PriorityQueue是线程安全的吗？（4）PriorityQueue就有序的吗？简介优先级队列，是0个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出优先... 查看详情
第五节：java集合框架之优先级队列priorityqueue（堆）(代码片段)
文章目录一：堆基本概念（1）什么是堆（2）堆存储方式二：堆的模拟实现（1）重点操作说明A：堆的初始化B：堆的向下调整C：堆的构造D：堆的插入E：堆的删除（2）代码... 查看详情
最大堆与堆排序和优先队列
基本概念：堆、树、最大堆关于堆和树由《算法导论》的描述，堆的本质是一个完全N叉树，它以数组作为元素的存储载体。这里注意和“堆内存”的概念做区分。一个二叉堆的结构如下图所示。包括堆的逻辑结构(A)和存储结构(B... 查看详情
优先级队列与堆排序
...Queue-And-Heap-Sort.html 在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该... 查看详情
堆和优先级队列2：java实现堆和优先级队列(代码片段)
1.什么是优先级队列在C++和java等库中，都提供了优先级队列这个容器，java中的优先级队列是PriorityQueue。其实底层就是一个堆的结构，只不过将堆封装了一层而已。其实名字叫个优先级队列，但总觉得和队列... 查看详情
java集合框架priorityqueue优先级队列的使用
文章目录1.场景引入2.PriorityQueue介绍3.知识点4.常用方法5.优先级队列插入元素的细节问题6.PriorityQueue大根堆的创建方式6.1思路6.2代码实现6.3使用匿名内部类1.场景引入我们知道，Queue是一个先进先出（FIFO）的队列。在... 查看详情
优先队列(堆)·二项队列
...logN)\\)。?二项队列：不是一棵堆序的树，而是堆序的树的集合，成为森林。森林的每棵树都是二项树(binomialtree)。每个 查看详情
前端必看js数据结构与算法(队列,链表,集合,字典,树,图,堆)(代码片段)
队列队列简介一个先进先出的数据结构js中没有队列,但是可以用Array实现对队列的所有功能使用数组模拟先进先出的场景constqueue=[]//进队列queue.push(1)queue.push(2)//出队列constitme1=queue.shift()constitme2=queue.shift()什么时候用食堂... 查看详情
《java数据结构》——优先级队列（小根堆的模拟实现）(代码片段)
...f1f;🌰举个例子队列是一种先进先出（FIFO）的数据结构，但是有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，在这种情况下使用队列就不行了，比... 查看详情
优先级队列（堆）(代码片段)
优先级队列（堆）优先级队列（PriorityQueue）优先级队列的概念在集合框架中所处的位置优先级队列的特性1.注意的点2.三种构造方法3.插入/删除/获取优先级最高的元素优先级队列的模拟实现1.堆的概念2.堆的存储方... 查看详情
优先级队列（堆）(代码片段)
优先级队列（堆）优先级队列（PriorityQueue）优先级队列的概念在集合框架中所处的位置优先级队列的特性1.注意的点2.三种构造方法3.插入/删除/获取优先级最高的元素优先级队列的模拟实现1.堆的概念2.堆的存储方... 查看详情