Java数据结构之优先级队列(堆)图文详解
作者:波风张三 发布时间:2021-06-25 13:47:58
一、堆的概念
堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时:
(1)ki >= k2i 且 ki >= k(2i+1) ——大根堆
(2) ki <= k2i 且 ki <= k(2i+1) ——小根堆
简单来说:
堆是具有以下性质的完全二叉树:
(1)每个结点的值都大于或等于其左右孩子结点的值,称为大根堆(如左下图);
或者:
(1)每个结点的值都小于或等于其左右孩子结点的值,称为小根堆(如右下图)。
我们使用数组保存二叉树结构,即是将二叉树用层序遍历方式放入数组中,如上图。
堆的元素下标存在以下关系:
1.假如已知双亲(parent)的下标,则
左孩子(left)下标 = 2parent + 1;
右孩子(right)下标 = 2parent +2;
2.已知孩子(child)(不区分左右)下标,则:
双亲(parent)下标 = (child - 1)/ 2 ;
小结:
堆逻辑上是一棵完全二叉树;
堆物理上保存在数组中;
满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆;反之,则是小堆,或者小根堆,或者最小堆;
堆的基本作用是,快速找集合中的最值。
二、向下调整
1.建初堆
设有一个无序序列 {2,5,7,8,4,6,3,0,9,1 },下面通过图解来建初始堆。
这里有一个前提:这棵二叉树的左右子树都必须是一个堆,才能进行调整。
下面是用到的数据的一些说明:
array 代表存储堆的数组
size 代表数组中被视为堆数据的个数
index 代表要调整位置的下标
left 代表 index 左孩子下标
right 代表 index 右孩子下标
min 代表 index 的最小值孩子的下标
过程文字描述如下:
1.index 如果已经是叶子结点,则整个调整过程结束:
(1)判断 index 位置有没有孩子;
(2) 因为堆是完全二叉树,没有左孩子就一定没有右孩子,所以判断是否有左孩子;
(3) 因为堆的存储结构是数组,所以判断是否有左孩子即判断左孩子下标是否越界,即 left >= size 越界。
2.确定 left 或 right,谁是 index 的最小孩子 min:
(1) 如果右孩子不存在,则 min = left;
(2)否则,比较 array[left] 和 array[right] 值得大小,选择小的为 min;
(3)比较 array[index] 的值 和 array[min] 的值,如果 array[index] <= array[min],则满足堆的性质,调整结束。
3.否则,交换 array[index] 和 array[min] 的值;
4.然后因为 min 位置的堆的性质可能被破坏,所以把 min 视作 index,向下重复以上过程。
通过上面的操作描述,我们写出以下代码:
public static void shiftDown(int[] array, int size, int index){
int left = 2*index +1;
while(left < size){
int min = left;
int right = 2*index +2;
if(right<size){
if(array[right] < array[left]){
min = right;
}
}
if(array[index] <= array[min]){
break;
}
int tmp = array[index];
array[index] = array[min];
array[min] = tmp;
index = min;
left = 2*index +1;
}
}
时间复杂度为 O(log(n))。
2.建堆
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
时间复杂度分析:
粗略估算,可以认为是在循环中执行向下调整,为 O(n * log(n)),(了解)实际上是 O(n)。
//建堆代码
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//调整
shiftDown(parent,usedSize);
}
}
三、优先级队列
1.什么是优先队列?
根据百科解释:
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出(first in, largest out)的行为特征。通常采用堆数据结构来实现。
所以我们在这里实现优先队列的内部原理是堆,也就是说采用堆来构建。
2.入队列
过程(以大堆为例):
首先按尾插方式放入数组;
比较其和其双亲的值的大小,如果双亲的值大,则满足堆的性质,插入结束;
否则,交换其和双亲位置的值,重新进行 2、3 步骤;
直到根结点。
下面图解:
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
3.出队列
为了防止破坏堆的结构,删除时并不是直接将堆顶元素删除,而是用数组的最后一个元素替换堆顶元素,然后通过向 下调整方式重新调整成堆。
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意这里传入的是usedSize-1
shiftUp(usedSize-1);
}
4.返回队首元素
直接返回堆顶元素
public int peek() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空!");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
整体的代码:
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下调整函数的实现
* @param parent 每棵树的根节点
* @param len 每棵树的调整的结束位置 10
*/
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起码 是有左孩子的,至少有1个孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保证当前左右孩子最大值的下标
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//调整
shiftDown(parent,usedSize);
}
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意这里传入的是usedSize-1
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize == elem.length;
}
public int poll() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空!");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public int peek() {
if(isEmpty()) {
throw new RuntimeException("优先级队列为空!");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
}
5.堆的其他TopK问题
什么是TopK问题?
从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。
解决这类问题,我们往往会有以下几种思路:
对整体进行排序,输出前10个最大的元素。
用上面刚刚讲的堆。
也是用堆,不过这比第二个思路更巧妙。
我们直接讲思路三:
先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。
直到,扫描完所有n-k个元素,最终堆中的k个元素,就是所要求的TopK。
以这个数组{12,15,21,41,30}为例,找到前3个最大的元素。
那如果是将一组进行从小到大排序,我们该采用大根堆还是小根堆?
答案是:大根堆!
步骤如下:
将这组数据调整为大根堆调整为大根堆;
0下标和最后1个未排序的元素进行交换即可;
重复1、2,直到结束。
总结:
如果求前K个最大的元素,要建一个小根堆。如果求前K个最小的元素,要建一个大根堆。第K大的元素。建一个小堆,堆顶元素就是第K大的元素。第K小的元素。建一个大堆,堆顶元素就是第K小的元素。
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起码 是有左孩子的,至少有1个孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保证当前左右孩子最大值的下标
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
来源:https://blog.csdn.net/weixin_46913665/article/details/122849413
猜你喜欢
- 1. 启动入口本系列RocketMQ4.8注释github地址,希望对大家有所帮助,要是觉得可以的话麻烦给点一下Star哈前面我们已经分析完
- 1.问题描述汉诺塔问题是一个经典的问题。汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说。大梵天创造世界的时候做了三根金刚
- 刚开始项目,需要用到mybatis分页,网上看了很多插件,其实实现原理基本都大同小异,但是大部分都只给了代码,注释不全,所以参考了很多篇文章
- 前言一个说难不难,说简单竟看不出来是哪里问题的一个bug。是的 可能自己能力和经验尚浅无法识别,下面你们能否用火眼金睛一眼让bug原形毕露(
- 本文实例讲述了Java继承Thread类创建线程类。分享给大家供大家参考,具体如下:一 点睛通过继承Thread类创建线程并启动多线程的步骤
- 前言这里主要简单介绍如何使用Camera+SurfaceView自定义相机拍照,如果是Camera2或者是TextureView的可以前往主
- 参考 java查找无向连通图中两点间所有路径的算法,对代码进行了部分修改,并编写了测试用例。算法要求:1. 在一个无向连通图中求出
- Interceptor 介绍 * (Interceptor)同 Filter 过滤器一样,它俩都是面向切面编程—&
- LinkedListLinkedList是一种可以在任何位置进行高效地插入和删除操作的有序序列。它的最基本存储结构是一个节点:每个节点将存储
- java调用外部程序的方法 在一个java应用中,可能会遇到这样的需求,就是需要调用一些外部的应用做一些处理,比如调用excel,
- 在 Java 中将 Object 转换为 Int我们可以使用 Object 类来引用我们在 Java 中不知道其类型的任
- Java5 在 java.util.concurrent 包中已经包含了读写锁。尽管如此,我们还是应该了解其实现背后的原理。读/写锁的 Ja
- 封装(Encapsulation)是面向对象编程的一个核心概念,它意味着将数据(属性)和方法(操作数据的函数)捆绑在一起,形成一个类(Cla
- pom.xml<dependency> <groupId>org.springframework.bo
- 首先是.select在MP查询中,默认查询所有的字段,如果有需要也可以通过select方法进行指定字段。其中要注意的细节:wrapper.s
- Seata介绍Seata:Simple Extensible Autonomous Transaction Architecture,简易可
- 异常的英文单词是exception,字面翻译就是“意外、例外”的意思,也就是非正常情况。事实上,异常本质上是程序上的错误,包括程序逻辑错误和
- Swagger以及knife4j基本使用Swagger 介绍:官网:https://swagger.io/Swagger是一个规范和完整的框
- 最近回顾了一下java继承中的问题,下面贴代码:public class Base {protected String temp = &qu
- 一、前言Redis是一个NoSQL(非关系型数据库)数据库之一,key-value存储系统或者说是一个缓存键值对数据库,具有如下特性:基于内