`
冰糖葫芦
  • 浏览: 293262 次
社区版块
存档分类
最新评论

java使用小根堆实现优先级队列的几种方式

阅读更多

写在之前

1.自定义实现采用数组作为内部数据结构

2.内部数组通过grow方法进行扩容,每次只是简单的扩展为原来的2倍

3.集中实现方式的主要区别在于siftDown方法

4.以下给出关键代码,更多详细信息请看附件源码

 

实现方式一(递归实现)

关键代码:

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        int left = left(index);
        int right = right(index);
        if(left > len)
        {
            return;
        }
        int currentMin = left;
        if(right <= len && arr[currentMin] > arr[right])
        {
            currentMin = right;
        }
        if(arr[currentMin] < arr[index])
        {
            swap(arr, currentMin, index);
            siftDown(currentMin);
        }
    }

  

实现方式二(循环实现)

关键代码:

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        while(left(index) <= len)
        {
            int left = left(index);
            int right = right(index);
            if(left > len)
            {
                break;
            }
            int currentMin = left;
            if(right <= len && arr[currentMin] > arr[right])
            {
                currentMin = right;
            }
            if(arr[currentMin] >= arr[index])
            {
                break;
            }
            swap(arr, currentMin, index);
            index = currentMin;
        }
    }

 

实现方式三(直接构建堆)

关键代码:

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        while(left(index) <= len)
        {
            int left = left(index);
            int right = right(index);
            if(left > len)
            {
                break;
            }
            int currentMin = left;
            if(right <= len && arr[currentMin] > arr[right])
            {
                currentMin = right;
            }
            if(arr[currentMin] < arr[index])
            {
                swap(arr, currentMin, index);
            }
            //进入下一个非叶子节点
            index++;
            
        }
    }

 

实现方式四(JDK中的实现)

1.siftUp方法:

protected void siftUp(int k, int x) 
    {
        while (k > 0) 
        {
            int parent = parent(k);
            int e = arr[parent];
            if (x >= e)
                break;
            arr[k] = e;
            k = parent;
        }
        arr[k] = x;
    }

 2.siftDown方法:

   /**
     * 指定index位置的值为x,并为x在堆中找到合适位置
     * @param index
     * @param x
     */
    private void siftDown(int index, int x) 
    {
        int half = totalCount >>> 1;        
        while (index < half) 
        {
            int currentMin = left(index);
            int right = right(index);
            if (right < totalCount && arr[currentMin] > arr[right])
                currentMin = right;
            if (x <= arr[currentMin])
                break;
            //将index位置设置为最小节点值
            arr[index] = arr[currentMin];
            //迭代
            index = currentMin;
        }
        //将最终值放入合适位置
        arr[index] = x;
    }

 

其他的一下关键方法

1.siftUp方法:

   @Override
    protected void siftUp(int index)
    {
        int parent = parent(index);
        while(index > 0 && arr[index] < arr[parent])
        {
            swap(arr, index, parent);
            index = parent;
            parent = parent(index);
        }
    }

 2.add方法:

   @Override
    public boolean add(int ele)
    {
        if(totalCount == arr.length)
        {
            //扩容
            grow();
        }
        
        int i = totalCount;
        arr[i] = ele;
        if(totalCount == 1)
        {
            return true;
        }
        
        //调整元素位置确保为小根堆
        siftUp(i);
        totalCount++;
        return true;
    }

 3.poll方法:

   @Override
    public int poll()
    {
        int result = arr[0];
        arr[0] = arr[--totalCount];
        siftDown(0);
        
        return result;
    }

 5.remove方法:

   @Override
    public int remove(int ele)
    {
        //内部数据为空
        if(totalCount < 1)
        {
            return -1;
        }
        
        //计算元素位置
        int index = indexOf(ele);
        if(index < 0)
        {
            return -1;
        }
        
        return removeAt(index);
    }

 6.removeAt方法:

   @Override
    protected int removeAt(int idx)
    {
        if(idx < 0 || idx >= totalCount)
        {
            return -1;
        }
        int result = arr[idx];
        
        //将删除元素与最后一个元素交换位置
        if(idx != totalCount -1)
        {
            arr[idx] = arr[totalCount - 1];
        }
        //位置交换之后队列长度减一
        totalCount--;
        //如果队列长度大于1,而且删除的元素位置不在队尾则重新调整堆
        if(totalCount > 1 && idx != totalCount)
        {
            siftDown(idx);
        }
        return result;
    }

 

 

 

0
0
分享到:
评论

相关推荐

    java数据结构与算法第二版

    几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...

    Java数据结构和算法中文第二版

    几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...

    基于java实现网络爬虫(蜘蛛)源码

    网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) ...

    Java数据结构和算法(第二版)

    几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除...

    Java数据结构和算法中文第二版(1)

    几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...

    基于java实现网络爬虫(蜘蛛)源码分享

    网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般只有以下几种情况: 1) 搜索引擎 2) 竞品调研 3) 舆情监控 4) 市场分析 网络爬虫的整体执行流程: 1) 确定一个(多个)种子网页 2) ...

    Java数据结构和算法中文第二版(2)

    几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...

    Java语言基础下载

    线程中断/恢复的几种方式 178 创建线程的两种方式 179 线程的控制 180 实例分析 182 内容总结 189 独立实践 190 第十二章:高级I/O流 192 学习目标 192 I/O基础知识 193 字节流 193 字符流 194 节点流 194 过程流 ...

    Java开发技术大全 电子版

    11.2.3优先队列(PriorityQueue)使用示例340 11.2.4哈希集合(HashSet)使用示例343 11.2.5哈希映射类(HashMap)使用示例347 11.2.6有序树(TreeSet)使用示例349 11.2.7有序树映射类(TreeMap)使用示例353 ...

    java范例开发大全源代码

    第1篇 Java编程基础  第1章 Java开发环境的搭建(教学视频:9分钟) 2  1.1 理解Java 2  1.2 搭建Java所需环境 3  1.2.1 下载JDK 3  1.2.2 安装JDK 4  1.2.3 配置环境 5  1.2.4 测试JDK配置...

    java范例开发大全

    第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...

    Java范例开发大全 (源程序)

    第1篇 Java编程基础  第1章 Java开发环境的搭建(教学视频:9分钟) 2  1.1 理解Java 2  1.2 搭建Java所需环境 3  1.2.1 下载JDK 3  1.2.2 安装JDK 4  1.2.3 配置环境 5  1.2.4 测试JDK配置是否成功 7...

    Java开发实战1200例(第1卷).(清华出版.李钟尉.陈丹丹).part3

    实例141 使用阻塞队列实现线程同步 183 实例142 新建有返回值的线程 184 实例143 使用线程池优化多线程编程 186 实例144 Object类中线程相关的方法 187 实例145 哲学家就餐问题 189 实例146 使用信号量实现线程同步 ...

    Java范例开发大全(全书源程序)

    Java范例开发大全(全书源程序),目录如下: 第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境...

    java范例开发大全(pdf&源码)

    第1篇 Java编程基础 第1章 Java开发环境的搭建(教学视频:9分钟) 2 1.1 理解Java 2 1.2 搭建Java所需环境 3 1.2.1 下载JDK 3 1.2.2 安装JDK 4 1.2.3 配置环境 5 1.2.4 测试JDK配置是否成功 7 实例1 开发第一个Java...

    强力 Java 爬虫,列表分页、详细页分页、ajax、微内核高扩展、配置灵活.rar

    网络爬虫是数据采集的一种方法,实际项目开发中,通过爬虫做数据采集一般有以下几种情况: 1)搜索引擎 2)竞品调研 3)舆情监控 4)市场分析 网络爬虫的整体执行流程 1)确定一个(多个)种子网页 2)进行数据的...

Global site tag (gtag.js) - Google Analytics