Java基于堆结构实现优先队列功能示例-6ren

Java基于堆结构实现优先队列功能示例

转载作者：qq735679552 更新时间：2022-09-28 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java基于堆结构实现优先队列功能示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考，具体如下:

 
    ? 
   
         package 
         Demo; 
        
         import 
         java.util.NoSuchElementException; 
        
         /* 
        
         * 小顶堆 java使用堆结构实现优先队列 
        
         */ 
        
         public 
         class 
         JPriorityQueue<E> { 
        
         @SuppressWarnings 
         ( 
         "hiding" 
         ) 
        
         class 
         QueueNode<E> { 
        
         int 
         capacity; 
        
         int 
         size; 
        
         E[] queue; 
        
         QueueNode( 
         int 
         capacity) { 
        
         this 
         .capacity = capacity; 
        
         } 
        
         } 
        
         QueueNode<E> node; 
        
         public 
         void 
         print() 
        
         { 
        
         E[] objs= 
         this 
         .node.queue; 
        
         for 
         ( 
         int 
         i= 
         0 
         ;i< 
         this 
         .node.size;i++) 
        
         { 
        
         System.out.print(objs[i]+ 
         " " 
         ); 
        
         } 
        
         System.out.println(); 
        
         } 
        
         @SuppressWarnings 
         ( 
         "unchecked" 
         ) 
        
         public 
         JPriorityQueue( 
         int 
         capacity) { 
        
         node =  
         new 
         QueueNode<E>(capacity); 
        
         node.size =  
         0 
         ; 
        
         node.queue = (E[])  
         new 
         Object[capacity +  
         1 
         ]; 
        
         } 
        
         public 
         void 
         add(E x) { 
        
         int 
         k = node.size; 
        
         while 
         (k >  
         0 
         ) { 
        
         int 
         parent = (k -  
         1 
         ) /  
         2 
         ; 
        
         E data = node.queue[parent]; 
        
         @SuppressWarnings 
         ({  
         "unchecked" 
         ,  
         "rawtypes" 
         }) 
        
         Comparable<E> key = (Comparable) x; 
        
         if 
         (key.compareTo(data) >=  
         0 
         ) 
        
         break 
         ; 
        
         node.queue[k] = data; 
        
         k = parent; 
        
         } 
        
         node.queue[k] = x; 
        
         node.size++; 
        
         } 
        
         public 
         E remove() { 
        
         int 
         parent =  
         0 
         ; 
        
         if 
         (node.size ==  
         0 
         ) { 
        
         throw 
         new 
         NoSuchElementException( 
         "queue is null" 
         ); 
        
         } 
        
         E min = node.queue[ 
         0 
         ]; 
         // top 
        
         E last = node.queue[node.size -  
         1 
         ]; 
         // last 
        
         node.queue[ 
         0 
         ] = last; 
         // add the last to top 
        
         node.queue[node.size -  
         1 
         ] =  
         null 
         ; 
        
         node.size--; 
        
         @SuppressWarnings 
         ( 
         "unchecked" 
         ) 
        
         Comparable<?  
         super 
         E> complast = (Comparable<?  
         super 
         E>) last; 
        
         if 
         (node.size ==  
         2 
         && complast.compareTo(node.queue[ 
         1 
         ]) >  
         0 
         ) {  
         // 只剩下最后两个结点，进行比较 
        
         node.queue[ 
         0 
         ] = node.queue[ 
         1 
         ]; 
        
         node.queue[ 
         1 
         ] = last; 
        
         } 
        
         if 
         (node.size >  
         2 
         ) {  
         // 大于三个结点的，向下旋转 
        
         while 
         (parent < node.size /  
         2 
         ) { 
        
         int 
         left =  
         2 
         * parent +  
         1 
         ; 
         // left child 
        
         int 
         right = left +  
         1 
         ; 
         // right child 
        
         E root = node.queue[parent]; 
        
         @SuppressWarnings 
         ( 
         "unchecked" 
         ) 
        
         Comparable<?  
         super 
         E> comproot = (Comparable<?  
         super 
         E>) root; 
        
         if 
         (comproot.compareTo(node.queue[left]) <  
         0 
        
         && comproot.compareTo(node.queue[right]) <  
         0 
         ) 
        
         break 
         ; 
        
         @SuppressWarnings 
         ( 
         "unchecked" 
         ) 
        
         Comparable<?  
         super 
         E> compleft = (Comparable<?  
         super 
         E>) node.queue[left]; 
        
         if 
         (compleft.compareTo(node.queue[right]) <=  
         0 
         ) { 
        
         node.queue[parent] = node.queue[left]; 
        
         node.queue[left] = root; 
        
         parent = left; 
        
         }  
         else 
         { 
        
         node.queue[parent] = node.queue[right]; 
        
         node.queue[right] = root; 
        
         parent = right; 
        
         } 
        
         if 
         (right *  
         2 
         >= node.size) 
        
         break 
         ; 
        
         } 
        
         } 
        
         return 
         min; 
        
         } 
        
         public 
         static 
         void 
         main(String[] args) { 
        
         System.out.println( 
         "我测试结果：" 
         ); 
        
         JPriorityQueue<String> queue =  
         new 
         JPriorityQueue<String>( 
         10 
         ); 
        
         queue.add( 
         "Z" 
         ); 
        
         queue.add( 
         "B" 
         ); 
        
         queue.add( 
         "QZA" 
         ); 
        
         queue.add( 
         "QBA" 
         ); 
        
         queue.add( 
         "EAA" 
         ); 
        
         queue.add( 
         "A" 
         ); 
        
         queue.print(); 
        
         // queue.remove(); 
        
         // queue.remove(); 
        
         // queue.remove(); 
        
         // queue.remove(); 
        
         // queue.remove(); 
        
         System.out.println(queue.remove()); 
        
         System.out.println(queue.remove()); 
        
         System.out.println(queue.remove()); 
        
         System.out.println(queue.remove()); 
        
         System.out.println(queue.remove()); 
        
         System.out.println(queue.remove()); 
        
         } 
        
         }

运行结果:

Java基于堆结构实现优先队列功能示例

希望本文所述对大家java程序设计有所帮助.

原文链接：http://blog.csdn.net/earbao/article/details/46275845 。

最后此篇关于Java基于堆结构实现优先队列功能示例的文章就讲到这里了,如果你想了解更多关于Java基于堆结构实现优先队列功能示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：误将.idea文件提交至git后删除的操作方法

文章推荐： java9区分opens与exports

文章推荐： spring boot+spring cache实现两级缓存(redis+caffeine)

文章推荐：快速解决idea打开某个项目卡住的问题

java - jms 队列 vs 内存中 java 队列
我遇到一种情况，我需要从某个主题读取(正在进行的)消息并将它们放入另一个 Queue 中。我怀疑我是否需要 jms Queue 或者我可以对内存中的 java Queue 感到满意。我将通过同一 jv
队列——数据结构严蔚敏C语言版
队列的定义队列(Queue):先进先出的线性表队列是仅在队尾进行插入和队头进行删除操作的线性表队头(front)：线性表的表头端,即可删除端队尾(rear)：线性表的表尾端,即可插入端由于这
Redis专题-队列
Redis专题-队列首先，想一想 Redis 适合做消息队列吗？ 1、消息队列的消息存取需求是什么？redis中的解决方案是什么？无非就是下面这几点： 0、数据可以顺序读
Python数据结构与算法（3.3）——队列
0. 学习目标栈和队列是在程序设计中常见的数据类型，从数据结构的角度来讲，栈和队列也是线性表，是操作受限的线性表，它们的基本操作是线性表操作的子集，但从数据类型的角度来讲，它们与线性表又有着巨大的不
Python Redis 队列
我想在 redis + Flask 和 Python 中实现一个队列。我已经用 RQ 实现了这样的查询，如果你有 Flask 应用程序和任务在同一台服务器上工作，它就可以正常工作。我想知道是否有可能创
用于多用户环境的 Laravel 队列
我正在使用 Laravel 5.1，我有一个大约需要 2 分钟来处理的任务，这个任务特别是生成报告...... 现在，很明显，我不能让用户在我接受用户输入的同一页面上等待 2 分钟，而是我应该在后台处
Azure 队列 - 我可以验证消息只会被读取一次吗？
我正在使用 Azure 队列，并且有多个不同的进程从队列中读取数据。我的系统的构建方式假设每条消息只读取一次。这个Microsoft article声称 Azure 队列具有至少一次传送保证，这可
multithreading - Perl线程::队列
我正在创建一个Thread::Queue元素数组。我这样做是这样的: for (my $i=0; $i new; } 但是，当我在每个队列中填充这样的元素时 $queues[$index]->enq
Mercurial 队列 - 备份和共享未提交的补丁
我试图了解如何将我的 Mercurial 补丁推送到远程存储库(例如 bitbucket.org)，而不必先应用它们(实际上提交它们)。我的动机是在最终完成之前首先对我的工作进行远程备份，并且能够与其
Mercurial 队列 - 导出补丁
我的本地计算机上有一个 Mercurial 队列补丁，我需要与同事共享该补丁，但我不想将其提交到上游存储库。有没有一种简单的方法可以打包该补丁并与他分享？最佳答案 mq 将补丁作为不带扩展名的文
Java "not removing"队列
Java 中是否有任何类提供与 Queue 相同的功能，但有返回对象的选项，并且不要删除它，只需将其设置在集合末尾？最佳答案 Queue不直接提供这样的方法。但是，您可以使用 poll 和 add
svn - svn一次全部提交(队列)？
我在Windows上使用Tortoise svn客户端，我需要能够一次提交来自不同子文件夹的更改文件-一次提交。像在提交之前将文件添加到队列中之类的？我该怎么做？ Windows上是否还有另一个svn
JAVA 队列 - 单元测试失败
好吧，我正在尝试对我的 DSAQueue 类进行单元测试，它显示我的 isEmpty()、isFull() 和 dequeue() 方法失败。以下是我的 DSAQueue 代码。我认为我的 Dequ
没有数据库查询的 laravel 队列
我想尽量减少对传入请求的数据库查询。它目前需要写入 6 个不同的表。在返回响应之前不需要完成处理。因此，我考虑了 laravel 队列，但我想知道我是否也可以摆脱写入队列/作业表所需的单独查询。我可以
Java 队列。该程序结果为空。
我正在学习队列数据结构。我想用链表创建队列。我想编程输出:10 20程序输出:队列为空-1 队列为空-1 我哪里出错了？代码如下: class Node { int x; Node next
java - 队列，优先级如何实现
“当工作人员有空时，他们会根据主题的优先级列表从等待请求池中进行选择。在时间 t 到达的所有请求都可以在时间 t 进行分配。如果两名工作人员同时有空，则安排优先权分配给最近的工作最早安排的人。如果仍然
jQuery:ESC 队列
我正在开发一个巨大的应用程序，它使用一些子菜单、模式窗口、提示等。现在，我想知道在此类应用程序中处理 Esc 和单击外部事件的正确方法。 $(document).keyup(function(e)
C 队列，按排序顺序复制元素
所以如果我有一个队列 a --> b --> NULL; 当我使用函数时 void duplicate(QueueNodePtr pHead, QueueNodePtr *pTail) 它会给 a
使用键盘输入创建 FIFO 队列
我正在尝试为键盘输入实现 FIFO 队列，但似乎无法让它工作。我可以让键盘输入显示在液晶显示屏上，但这就是我能做的。我认为代码应该读取键盘输入并将其插入队列，然后弹出键盘输入并将值读取到液晶屏幕上。有
JavaScript 队列 native
我正在学习算法和 DS。如何在 JavaScript 中使用队列？我知道你可以做这样的事情。 var stack = []; stack.push(2); // stack is now

qq735679552

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

Java基于堆结构实现优先队列功能示例