Java堆&优先级队列示例讲解(上)

目录
  • 1. 二叉树的顺序存储
    • 1.1 存储方式
    • 1.2 下标关系
  • 2. 堆(heap)
    • 2.1 概念
    • 2.2 操作-(下沉&上浮)本例是最大堆
    • 2.3 建堆-完整代码(最大堆)
  • 3. 优先级队列

1. 二叉树的顺序存储

1.1 存储方式

使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。

一般只适合表示完全二叉树,这种方式的主要用法就是堆的表示。

因为非完全二叉树会有空间的浪费(所有非完全二叉树用链式存储)。

1.2 下标关系

已知双亲 (parent) 的下标,则:

左孩子 (left) 下标 = 2 * parent + 1;

右孩子 (right) 下标 = 2 * parent + 2;

已知孩子(不区分左右) (child) 下标,则:

双亲 (parent) 下标 = (child - 1) / 2;

2. 堆(heap)

2.1 概念

1. 堆逻辑上是一棵完全二叉树

2. 堆物理上是保存在数组中

3. 满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆

4. 反之,则是小堆,或者小根堆,或者最小堆

5. 堆的基本作用是,快速找集合中的 最值

2.2 操作-(下沉&上浮)本例是最大堆

元素下沉:

     /**
     * 下沉操作
     */
    public void siftDown(int k){
        //还存在子树
        while (leftChild(k) < data.size()){
            int j = leftChild(k);
            //判断是否存在右子树且大于左子树的值
            if(j+1 < data.size() && data.get(j+1) > data.get(j)){
                j=j+1;
            }
            //此时j为左右子树最大值
            //和当前节点比较大小
            if(data.get(j) <= data.get(k)){
                break;
            }else {
                swap(k,j);
                k=j;
            }
        }
    }

元素上浮:

    /**
     * 上浮操作
     */
    // 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
    // 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
    private void siftUp(int k) {
        while (k>0 && data.get(k)>data.get(parent(k))){
            swap(k,parent(k));
            k=parent(k);
        }
    }

其中swap方法是交换操作:

    //交换三连
    private void swap(int i,int j) {
        int temp = data.get(j);
        data.set(j,data.get(i));
        data.set(i,temp);
    }

堆化数组:

    /**
     * 将任意数组堆化
     * @param arr
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        // 1.先将arr的所有元素复制到data数组中
        for(int i : arr){
            data.add(i);
        }
        // 2.从最后一个非叶子结点开始进行siftDown
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }

图示:

以此数组为例:

// 调整前
int[] array = { 27,15,19,18,28,34,65,49,25,37 };
// 调整后
int[] array = { 15,18,19,25,28,34,65,49,27,37 };

时间复杂度分析:

最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度

即时间复杂度为 O(log(n))

2.3 建堆-完整代码(最大堆)

/**
 * 基于整形最大堆实现
 * 时根节点从0开始编号,若此时节点编号为k
 * 左孩子为2k+1
 * 右孩子为2k+2
 * 父节点为(k-1)/2
 */

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxHeap {
    // 使用JDK的动态数组(ArrayList)来存储一个最大堆
    List<Integer> data;

    // 构造方法的this调用
    public MaxHeap(){
        this(10);
    }

    // 初始化的堆大小
    public MaxHeap(int size){
        data = new ArrayList<>(size);
    }

    /**
     * 将任意数组堆化
     * @param arr
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        // 1.先将arr的所有元素复制到data数组中
        for(int i : arr){
            data.add(i);
        }
        // 2.从最后一个非叶子结点开始进行siftDown
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }

    /**
     * 向最大堆中增加值为Value的元素
     * @param value
     */
    public void add(int value){
        //1.先直接加到堆的末尾
        data.add(value);
        //2.元素上浮操作
        siftUp(data.size()-1);
    }

    /**
     * 只找到堆顶元素值
     * @return
     */
    public int peekMax (){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot peek");
        }
        return data.get(0);
    }

    /**
     * 取出当前最大堆的最大值
     */
    public int extractMax(){
        // 取值一定注意判空
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot extract");
        }
        int max = data.get(0);
        // 1.将数组末尾元素顶到堆顶
        int lastValue =data.get(data.size()-1);
        data.set(0,lastValue);
        // 2.将数组末尾的元素删除
        data.remove(data.size()-1);
        // 3.进行元素的下沉操作
        siftDown(0);
        return max;
    }

    /**
     * 下沉操作
     */
    public void siftDown(int k){
        //还存在子树
        while (leftChild(k) < data.size()){
            int j = leftChild(k);
            //判断是否存在右子树且大于左子树的值
            if(j+1 < data.size() && data.get(j+1) > data.get(j)){
                j=j+1;
            }
            //此时j为左右子树最大值
            //和当前节点比较大小
            if(data.get(j) <= data.get(k)){
                break;
            }else {
                swap(k,j);
                k=j;
            }
        }
    }

    /**
     * 上浮操作
     */
    // 上浮操作的终止条件: 已经走到根节点 || 当前节点值 <= 父节点值
    // 循环的迭代条件 : 还存在父节点并且当前节点值 > 父节点值
    private void siftUp(int k) {
        while (k>0 && data.get(k)>data.get(parent(k))){
            swap(k,parent(k));
            k=parent(k);
        }
    }

    //交换三连
    private void swap(int i,int j) {
        int temp = data.get(j);
        data.set(j,data.get(i));
        data.set(i,temp);
    }

    //判读堆为空
    public boolean isEmpty(){
        return data.size() == 0;
    }
    //根据索引找父节点
    public int parent(int k){
        return (k-1)>>1;
    }
    //根据索引找左孩子
    public int leftChild(int k){
        return k<<2+1;
    }
    //根据索引找右孩子
    public int rightChild(int k){
        return k<<2+2;
    }

    @Override
    public String toString() {
        return data.toString();
    }
}

ps:随机数操作

        int[] data=new int[10000];
        //随机数
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt();
        }

3. 优先级队列

详见下节:Java堆&优先级队列示例讲解(下)

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

(0)

相关推荐

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

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

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

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

  • 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数据结构和算法之堆

    目录 1.堆的定义 2.遍历和查找 3.移除 4.插入 5.完整的Java堆代码 总结 1.堆的定义 ①.它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的.注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树. ②.它通常用数组来实现. 这种用数组实现的二叉树,假设节点的索引值为index,那么: 节点的左子节点是 2*index+1, 节点的右子节点是 2*index+2, 节点的父节点是 (index-1)/2. ③.堆中的每一个节点的关键字

  • Java堆&优先级队列示例讲解(上)

    目录 1. 二叉树的顺序存储 1.1 存储方式 1.2 下标关系 2. 堆(heap) 2.1 概念 2.2 操作-(下沉&上浮)本例是最大堆 2.3 建堆-完整代码(最大堆) 3. 优先级队列 1. 二叉树的顺序存储 1.1 存储方式 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中. 一般只适合表示完全二叉树,这种方式的主要用法就是堆的表示. 因为非完全二叉树会有空间的浪费(所有非完全二叉树用链式存储). 1.2 下标关系 已知双亲 (parent) 的下标,则: 左孩子

  • Java堆&优先级队列示例讲解(下)

    目录 1.优先级队列 1.1 概念 1.2 内部原理 1.3 操作-入队列 1.4 操作-出队列(优先级最高) 1.5 借用堆实现优先级队列 1.6 测试 1.优先级队列 1.1 概念 在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象.最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话.在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象.这种数据结构

  • Java线程优先级变量及功能

    目录 前言: Java线程优先级示例 Java线程优先级的优势 结论 前言: 线程被称为“最小的处理单元”,是一个轻量级的子进程,分配了一些需要执行的工作.线程共享分配给它们的相同内存插槽,并且彼此独立,因此促进了多任务处理.但是,当多个线程在共享内存插槽上运行时,必然会发生资源竞争.为了避免这种竞争,从而实现高吞吐量,引入了线程优先级的概念.当多个任务在同一个系统上运行时,它具有重要意义.“线程调度器根据优先级分配执行线程”. JVM(JAVA虚拟机)默认或由程序员明确地决定线程的优先级.优先

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

  • java实现网页爬虫的示例讲解

    这一篇目的就是在于网页爬虫的实现,对数据的获取,以便分析. 目录: 1.爬虫原理 2.本地文件数据提取及分析 3.单网页数据的读取 4.运用正则表达式完成超连接的连接匹配和提取 5.广度优先遍历,多网页的数据爬取 6.多线程的网页爬取 7.总结 爬虫实现原理 网络爬虫基本技术处理 网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) 进

  • 解析Java中PriorityQueue优先级队列结构的源码及用法

    一.PriorityQueue的数据结构 JDK7中PriorityQueue(优先级队列)的数据结构是二叉堆.准确的说是一个最小堆. 二叉堆是一个特殊的堆, 它近似完全二叉树.二叉堆满足特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆. 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆. 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆. 下图是一个最大堆 priorityQueue队头就是给定顺序的最小元素. prio

  • Python cookbook(数据结构与算法)实现优先级队列的方法示例

    本文实例讲述了Python实现优先级队列的方法.分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素: 解决方案:采用heapq模块实现一个简单的优先级队列 # example.py # # Example of a priority queue import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index =

  • hadoop中实现java网络爬虫(示例讲解)

    这一篇网络爬虫的实现就要联系上大数据了.在前两篇java实现网络爬虫和heritrix实现网络爬虫的基础上,这一次是要完整的做一次数据的收集.数据上传.数据分析.数据结果读取.数据可视化. 需要用到 Cygwin:一个在windows平台上运行的类UNIX模拟环境,直接网上搜索下载,并且安装: Hadoop:配置Hadoop环境,实现了一个分布式文件系统(Hadoop Distributed File System),简称HDFS,用来将收集的数据直接上传保存到HDFS,然后用MapReduce

随机推荐