Java数据结构之优先级队列(堆)图文详解

目录
  • 一、堆的概念
  • 二、向下调整
    • 1.建初堆
    • 2.建堆
  • 三、优先级队列
    • 1.什么是优先队列?
    • 2.入队列
    • 3.出队列
    • 4.返回队首元素
    • 5.堆的其他TopK问题
  • 总结:
  • 总结

一、堆的概念

堆的定义: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个最大的元素。
  • 用上面刚刚讲的堆。
  • 也是用堆,不过这比第二个思路更巧妙。

我们直接讲思路三:

  1. 先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
  2. 接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。
  3. 直到,扫描完所有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;
            }
        }
    }

总结

来来回回,这篇文章写了2-3天了,以前写文章总是蜻蜓点水,不到水深,导致自己对很多的知识也没有多深理解,仅仅是为了写文章而写文章。希望有改变,从这篇文章开始吧!

到此这篇关于Java数据结构之优先级队列(堆)的文章就介绍到这了,更多相关Java优先级队列(堆)内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数组模拟优先级队列数据结构的实例

    优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先

  • 详谈java 堆区、方法区和栈区

    堆区:只存放类对象,线程共享: 方法区:又叫静态存储区,存放class文件和静态数据,线程共享; 栈区:存放方法局部变量,基本类型变量区.执行环境上下文.操作指令区,线程不共享; class A { private String a = "aa"; //a在堆区 public boolean methodB() { String b = "bb"; //b在栈区 final String c = "cc"; // c在栈区 } } 以上这篇详谈j

  • Java深入了解数据结构之优先级队列(堆)

    目录 一,二叉树的顺序存储 ①存储方式 ②下标关系 ③二叉树顺序遍历 二,堆 ①概念 ②操作-向下调整 ③建堆(建大堆为例) 三,堆的应用-优先级队列 ①概念 ②内部原理 ③入队列 ④出队列(优先级最高) ⑤返回队首元素(优先级最高) 四,堆排序 一,二叉树的顺序存储 ①存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费. 这种方式的主要用法就是堆的表示. ②下标关系 已知双亲(parent)的下标,则: 左孩子(

  • Java 堆排序实例(大顶堆、小顶堆)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. 堆排序的平均时间复杂度为Ο(nlogn) . 算法步骤: 1. 创建一个堆H[0..n-1] 2. 把堆首(最大值)和堆尾互换 3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 4. 重复步骤2,直到堆的尺寸为1 堆: 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:

  • Java中堆和栈的区别详解

    当一个人开始学习Java或者其他编程语言的时候,会接触到堆和栈,由于一开始没有明确清晰的说明解释,很多人会产生很多疑问,什么是堆,什么是栈,堆和栈有什么区别?更糟糕的是,Java中存在栈这样一个后进先出(Last In First Out)的顺序的数据结构,这就是java.util.Stack.这种情况下,不免让很多人更加费解前面的问题.事实上,堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存.众所周知,所有的Java程序都运行在JVM虚拟机内部,我们这里介绍的自然

  • java实现堆的操作方法(建堆,插入,删除)

    如下所示: import java.util.Arrays; //小顶堆的代码实现 public class Heap { // 向下调整,顶端的大值往下调,主要用于删除和建堆,i表示要调整的节点索引,n表示堆的最有一个元素索引 // 删除时候,i是0,建堆时候i从最后一个节点的父节点依次往前调整 public static void fixDown(int[] data, int i, int n) { int num = data[i]; int son = i * 2 + 1; while

  • Java数据结构之优先级队列(堆)图文详解

    目录 一.堆的概念 二.向下调整 1.建初堆 2.建堆 三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题 总结: 总结 一.堆的概念 堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆 简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的

  • Java数据结构之优先级队列(PriorityQueue)用法详解

    目录 概念 PriorityQueue的使用 小试牛刀(最小k个数) 堆的介绍 优先级队列的模拟实现 Top-k问题 概念 优先级队列是一种先进先出(FIFO)的数据结构,与队列不同的是,操作的数据带有优先级,通俗的讲就是可以比较大小,在出队列的时候往往需要优先级最高或者最低的元素先出队列,这种数据结构就是优先级队列(PriorityQueue) PriorityQueue的使用 构造方法 这里只介绍三种常用的构造方法 构造方法 说明 PriorityQueue() 不带参数,默认容量为11 P

  • Python数据结构之优先级队列queue用法详解

    一.基本用法 Queue类实现了一个基本的先进先出容器.使用put()将元素增加到这个序列的一端,使用get()从另一端删除.具体代码如下所示: import queue q = queue.Queue() for i in range(1, 10): q.put(i) while not q.empty(): print(q.get(), end=" ") 运行之后,效果如下: 这里我们依次添加1到10到队列中,因为先进先出,所以出来的顺序也与添加的顺序相同. 二.LIFO队列 既然

  • Java栈和基础队列的实现详解

    目录 栈(stack) 栈支持的三个核心操作: 栈的常见实际应用: 栈的实现 队列 无论是哪种队列,都必须支持三个核心操作: 基础队列的实现 栈和队列:都是线性表,都是基于List基础上的实现 线性表:数组,链表,字符串,栈,队列 元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素 栈(stack) 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)

  • Java数据结构之有向图的拓扑排序详解

    目录 前言 拓扑排序介绍 检测有向图中的环 实现思路 API设计 代码实现 基于深度优先的顶点排序 实现思路 API设计 代码实现 拓扑排序 API设计 代码实现 测试验证 前言 在现实生活中,我们经常会同一时间接到很多任务去完成,但是这些任务的完成是有先后次序的.以我们学习java 学科为例,我们需要学习很多知识,但是这些知识在学习的过程中是需要按照先后次序来完成的.从java基础,到 jsp/servlet,到ssm,到springboot等是个循序渐进且有依赖的过程.在学习jsp前要首先掌

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

  • Java数据结构之有向图设计与实现详解

    目录 前言 定义及相关术语 API设计 代码实现 前言 在实际生活中,很多应用相关的图都是有方向性的,最直观的就是网络,可以从A页面通过链接跳转到B页面,那么a和b连接的方向是a->b,但不能说是b->a,此时我们就需要使用有向图来解决这一类问题,它和我们之前学习的无向图,最大的区别就在于连接是具有方向的,在代码的处理上也会有很大的不同. 定义及相关术语 定义: 有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点. 出度: 由某个顶点指出的边的个数

  • java 数据结构之堆排序(HeapSort)详解及实例

    1 堆排序 堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整.最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点. 所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

随机推荐