关键词：
Java集合与数据结构 优先级队列【堆】
二叉树的顺序存储
存储方式
使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的主要用法就是堆的表示。
下标关系：
已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;
堆(heap)
概念：
- 堆逻辑上是一棵完全二叉树。
- 堆物理上是保存在数组中。
- 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆。
- 反之，则是小堆，或者小根堆，或者最小堆。
- 堆的基本作用是：快速找集合中的最值。
操作-向下调整
前提：左右子树必须已经是一个堆，才能调整。
说明：
- array 代表存储堆的数组。
- size 代表数组中被视为堆数据的个数。
- index 代表要调整位置的下标。
- left 代表 index 左孩子下标。
- right 代表 index 右孩子下标。
- max 代表 index 的最大值孩子的下标。
过程（以大堆为例）：
- index 如果已经是叶子结点，则整个调整过程结束。
- 判断 index 位置有没有孩子。
- 因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以判断是否有左孩子
- 因为堆的存储结构是数组，所以判断是否有左孩子即判断左孩子下标是否越界，即 left >= size 越界。
- 确定 left 或 right，谁是 index 的最大孩子 max。
- 如果右孩子不存在，则 max = left。
- 否则，比较 array[left] 和 array[right] 值得大小，选择大的为 max。
- 比较 array[index] 的值 和 array[max] 的值，如果 array[index] >= array[max]，则满足堆的性质，调整结束。
- 否则，交换 array[index] 和 array[max] 的值。
- 然后因为 max 位置的堆的性质可能被破坏，所以把 max 视作 index，向下重复以上过程。
逻辑代码：
public class HeapDemo
public int[] elem;
public int usedSize;
public HeapDemo()
this.elem = new int[10];
//时间复杂度分析：最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度即时间复杂度为 O(log(n))
public void adjustDown(int parent, int len)
int child = 2 * parent + 1;
while (child < len)
if (child+1 < len && this.elem[child] < this.elem[child+1])
child++;
if (this.elem[child] > this.elem[parent])
int temp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = temp;
parent = child;
child = 2*parent+1;
else
break;
//时间复杂度分析：时间复杂度为 O(n * log(n))，实际上是 O(n)。
public void createBigHeap(int[] array)
for (int i = 0; i < array.length; i++)
this.elem[i] = array[i];
this.usedSize++;
for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--)
adjustDown(i, this.usedSize);
public void show()
for (int i = 0; i < this.usedSize; i++)
System.out.print(this.elem[i] + " ");
System.out.println();
测试代码：
public class TestDemo
public static void main(String[] args)
HeapDemo heapDemo = new HeapDemo();
int[] array = 27,15,19,18,28,34,65,49,25,37;
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
System.out.println();
heapDemo.createBigHeap(array);
heapDemo.show();
该代码的执行结果为：
堆的应用-优先级队列
概念：
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。
内部原理
优先级队列的实现方式有很多，但最常见的是使用堆来构建。
操作-入队列
过程（以大堆为例）：
- 首先按尾插方式放入数组
- 比较其和其双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
- 否则，交换其和双亲位置的值，重新进行 2、3 步骤
- 直到根结点
逻辑代码：
public void adjustUp(int child)
int parent = (child - 1) / 2;
while (child > 0)
if (this.elem[child] > this.elem[parent])
int temp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = temp;
child = parent;
parent = (child - 1) / 2;
else
break;
public void push(int val)
if (isFull())
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
this.elem[this.usedSize] = val;
this.usedSize++;
adjustUp(this.usedSize - 1);
public boolean isFull()
return this.usedSize == this.elem.length;
操作-出队列
过程（以大堆为例）：
- 将第一个元素与最后一个元素进行交换。
- 删除最后一个下标
- 向下调整（只需要调整0号下标）
逻辑代码：
public int poll()
if (isEmpty())
throw new RuntimeException("队列为空~");
int ret = this.elem[0];
int temp = this.elem[0];
this.elem[0] = this.elem[usedSize-1];
this.elem[usedSize-1] = temp;
this.usedSize--;
adjustDown(0,this.usedSize);
return ret;
public boolean isEmpty()
return this.usedSize == 0;
public void adjustDown(int parent, int len)
int child = 2 * parent + 1;
while (child < len)
if (child + 1 < len && this.elem[child] < this.elem[child + 1])
child++;
if (this.elem[child] > this.elem[parent])
int temp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = temp;
parent = child;
child = 2 * parent + 1;
else
break;
java 中的优先级队列
PriorityQueue implements Queue
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：Comparble和Comparator两种方式。
- Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法。
- 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。
堆的其他应用 TopK 问题
问题描述： 从array[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
前k个最小的元素，建大堆；
前k个最大的元素，建小堆。
例如：从int[] array = 27,15,19,18,28,34,65,49,25,37 ;中找出最大的三个数。
逻辑代码：
public class HeapDemo
public int[] elem;
public int usedSize;
public HeapDemo()
this.elem = new int[10];
/*
找前k个最大的元素
创建小堆
*/
public static void topK(int[] array,int k)
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>()
@Override
public int compare(Integer o1, Integer o2)
return o1-o2;
);
for (int i = 0; i < array.length; i++)
if (minHeap.size() < k)
minHeap.offer(array[i]);
else
int top = minHeap.peek();
if (array[i] > top)
minHeap.poll();
minHeap.offer(array[i]);
for (int i = 0; i < k; i++)
System.out.println(minHeap.poll());
调试代码：
public class TestDemo
public static void main(String[] args)
int[] array = 27,15,19,18,28,34,65,49,25,37;
HeapDemo.topK(array,3);
该代码的执行结果为：
可见，该数组中最大的三个数已找到。
例如：从int[] array = 27,15,19,18,28,34,65,49,25,37 ;中找出最小的三个数。
逻辑代码：
public class HeapDemo
public int[] elem;
public int usedSize;
public HeapDemo()
this.elem = new int[10];
/*
找前k个最小的元素
创建大堆
*/
public static void minTopK(int[] array,int k)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>()
@Override
public int compare(Integer o1, Integer o2)
return o2-o1;
);
for (int i = 0; i < array.length; i++)
if (maxHeap.size() < k)
maxHeap.offer(array[i]);
else
Integer top = maxHeap.peek();
if (top != null)
if (array[i] < top)
maxHeap.poll();
maxHeap.offer(array[i]);
for (int i = 0; i < k; i++)
System.out.println(maxHeap.poll());
调试代码：
public class TestDemo
public static void main(String[] args)
int[] array = 27,15,19,18,28,34,65,49,25,37;
HeapDemo.minTopK(array,3);
该代码的执行结果为：
可见，该数组中最小的三个数已找到。
堆的其他应用 堆排序
基本原理是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆。
时间复杂度：不管是最好的情况还是最坏的情况都是O(n * log(n)) 。
空间复杂度：O(1)。
以排升序为例，逻辑代码：
public class HeapDemo
public int[] elem;
public int usedSize;
public HeapDemo()
this.elem = new int[10];
public void adjustDown(int parent, int len)
int child = 2 * parent + 1;
while (child < len)
if (child + 1 < len && this.elem[child] < this.elem[child + 1])
child++;
if (this.elem[child] > this.elem[parent])
int temp = this.elem[child];
this.elem[child] = this.elem[parent];
this.elem[parent] = temp;
parent = child;
child = 2 * parent + 1;
else
break;
public void createBigHeap(int[] array)
for (int i = 0; i < array.length; i++)
this.elem[i] = array[i];
this.usedSize++;
for (int i = (this.usedSize - 1 - 1) / 2; i >= 0; i--)
adjustDown(i, this.usedSize);
public void show()
for (int i = 0; i < this.usedSize; i查看详情
java集合数据结构——优先级队列(堆priorityqueue)(代码片段)
文章目录一、二叉树的顺序存储1.存储方式2.父亲和孩子的下标关系二、堆(heap)1.堆的基本概念2.堆的操作(1)建堆（向下调整）(2)建堆的时间复杂度(3)入队（向上调整）(4)出队（向下调整）三、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... 查看详情
优先级队列（堆）(代码片段)
...的概念我们都知道队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时可能需要优先级高的元素出队列，此时队列就显得不合适了。因此我们引入优先级队... 查看详情
优先级队列（堆）(代码片段)
...的概念我们都知道队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时可能需要优先级高的元素出队列，此时队列就显得不合适了。因此我们引入优先级队... 查看详情
数据结构java数据结构----堆(优先级队列)(代码片段)
文章目录堆(优先级队列)1.二叉树的顺序存储1.1存储方式1.2下标的关系2.堆2.1概念3.模拟实现PriorityQueue①基本操作②向下调整③建堆④入队列⑤出队列⑥堆排序4.堆的应用-优先级队列4.1java中的优先级队列4.2java中堆的使用5.集合框... 查看详情
第五节：java集合框架之优先级队列priorityqueue（堆）(代码片段)
文章目录一：堆基本概念（1）什么是堆（2）堆存储方式二：堆的模拟实现（1）重点操作说明A：堆的初始化B：堆的向下调整C：堆的构造D：堆的插入E：堆的删除（2）代码... 查看详情
java集合与数据结构——优先级队列的使用及练习
...头的重量未完待续…本文内容介绍大纲接上篇Java集合与数据结构——优先级队列（堆）一、对象比较的方法 上节课我们讲了优先级队列，优先级队列在插入元素时有个要求&#x 查看详情
优先级队列（堆）(代码片段)
优先级队列（堆）优先级队列（PriorityQueue）优先级队列的概念在集合框架中所处的位置优先级队列的特性1.注意的点2.三种构造方法3.插入/删除/获取优先级最高的元素优先级队列的模拟实现1.堆的概念2.堆的存储方... 查看详情
优先级队列（堆）(代码片段)
优先级队列（堆）优先级队列（PriorityQueue）优先级队列的概念在集合框架中所处的位置优先级队列的特性1.注意的点2.三种构造方法3.插入/删除/获取优先级最高的元素优先级队列的模拟实现1.堆的概念2.堆的存储方... 查看详情
堆和优先级队列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）的队列。在... 查看详情
前端必看js数据结构与算法(队列,链表,集合,字典,树,图,堆)(代码片段)
队列队列简介一个先进先出的数据结构js中没有队列,但是可以用Array实现对队列的所有功能使用数组模拟先进先出的场景constqueue=[]//进队列queue.push(1)queue.push(2)//出队列constitme1=queue.shift()constitme2=queue.shift()什么时候用食堂... 查看详情
数据结构--优先队列(堆排序)(代码片段)
数据结构--优先队列(堆排序)优先队列：不是先进先出啦，下面的代码是大顶堆，大的先出。在之前理解堆排序的基础上，在来理解优先队列。还是用这个公式： leftNo=parentNo*2+1 rightNo=parentNo*2+2 parentNo=(nodeNo-1)/2每次进... 查看详情
数据结构和算法-堆(代码片段)
...插入操作时，可以选择堆来实现优先级队列。2.java的堆和数据结构堆 查看详情
优先级队列（堆）(代码片段)
...目录内部原理操作步骤 向下调整 操作入队列概念 数据结构应该提供两个最基本的操作，一个是返回最高级优先级对象，一个是添加新的对象。这种数据结构就是优先级队列（PriorityQueue）堆逻辑上是一个完... 查看详情
优先队列及（二叉）堆(代码片段)
数据结构书籍与算法书（包括算法导论、算法设计）通常将优先队列(PriorityQueue)与堆(Heap)放在一起讲，算法导论上先讲堆这个特殊的数据结构，后讲堆的两个应用，堆排序与优先队列。算法设计这本书先讲优先队列是个什么... 查看详情
数据结构java版堆和优先级队列（超详解）(代码片段)
文章目录1.二叉树的顺序存储1.1存储方式1.2下标关系1.3顺序存储和堆的关系2.堆2.1概念2.2堆的创建（以大根堆为例）2.3创建堆的时间复杂度（易错）3.堆的应用（1）优先级队列3.1概念3.2内部原理3.3入队列操... 查看详情