priorityqueue（优先级队列的实例）

本文目录

• 优先级队列的实例
• 如何使用queue
• PriorityQueue使用求助

优先级队列的实例

有限的元素集合,每个元素都有一个优先权操作Create ( ):创建一个空的优先队列Size ( ):返回队列中的元素数目Max ( ):返回具有最大优先权的元素I n s e rt (x):将x插入队列DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x}优先队列插入元素的复杂度都是O(lgn)，删除元素的复杂度是O(1)，所以很快。另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).例：假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间(即具有最高优先权)的用户提供服务.如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。typePriorityQueue = recordcontents: array ;　　}　　　　bool UnorderedArrayQuene::isEmpty()　　{　　return N == 0; 　　}　　　　int main()　　{　　UnorderedArrayQuene Q;　　Q.Push(6);　　Q.Push(9);　　Q.Push(8);　　Q.Push(2);　　　　while(!Q.isEmpty())　　{　　std::cout《《Q.DeleteMaxElement()《《,;　　}　　system(pause);　　return 0;　　}

如何使用queue

Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue 继承了Queue接口。 队列是一种数据结构．它有两个基本操作：在队列尾部加人一个元素，和从队列头部移除一个元素就是说，队列以一种先进先出的方式管理数据，如果你试图向一个 已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索，将导致线程阻塞．在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可 以定期地把中间结果存到阻塞队列中而其他工作者线线程把中间结果取出并在将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个 线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。下表显示了jdk1.5中的阻塞队列的操作： add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满，则返回falsepoll 移除并返问队列头部的元素 如果队列为空，则返回nullpeek 返回队列头部的元素 如果队列为空，则返回nullput 添加一个元素 如果队列满，则阻塞take 移除并返回队列头部的元素 如果队列为空，则阻塞 remove、element、offer 、poll、peek 其实是属于Queue接口。 阻塞队列的操作可以根据它们的响应方式分为以下三类：aad、removee和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然，在多线程程序中，队列在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时 只是给出一个出错示而不会抛出异常。 注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。 还有带超时的offer和poll方法变种，例如，下面的调用：boolean success = q.offer(x,100,TimeUnit.MILLISECONDS);尝试在100毫秒内向队列尾部插入一个元素。如果成功，立即返回true；否则，当到达超时进，返回false。同样地，调用：Object head = q.poll(100, TimeUnit.MILLISECONDS);如果在100毫秒内成功地移除了队列头元素，则立即返回头元素；否则在到达超时时，返回null。 最后，我们有阻塞操作put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。 java.ulil.concurrent包提供了阻塞队列的4个变种。默认情况下，LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。ArrayBlockingQueue在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。PriorityBlockingQueue是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。最后，DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。 下面是延迟接口：Java代码public interface Delayed extends Comparable《Delayed》 { long getDelay(TimeUnit unit); } 放入DelayQueue的元素还将要实现compareTo方法，DelayQueue使用这个来为元素排序。 下面的实例展示了如何使用阻塞队列来控制线程集。程序在一个目录及它的所有子目录下搜索所有文件，打印出包含指定关键字的文件列表。从下面实例可以看出，使用阻塞队列两个显著的好处就是：多线程操作共同的队列时不需要额外的同步，另外就是队列会自动平衡负载，即那边（生产与消费两边）处理快了就会被阻塞掉，从而减少两边的处理速度差距。下面是具体实现：Java代码public class BlockingQueueTest { public static void main(String args) { Scanner in = new Scanner(System.in); System.out.print(“Enter base directory (e.g. /usr/local/jdk5.0/src): “); String directory = in.nextLine(); System.out.print(“Enter keyword (e.g. volatile): “); String keyword = in.nextLine(); final int FILE_QUEUE_SIZE = 10;// 阻塞队列大小 final int SEARCH_THREADS = 100;// 关键字搜索线程个数 // 基于ArrayBlockingQueue的阻塞队列 BlockingQueue《File》 queue = new ArrayBlockingQueue《File》( FILE_QUEUE_SIZE); //只启动一个线程来搜索目录 FileEnumerationTask enumerator = new FileEnumerationTask(queue, new File(directory)); new Thread(enumerator).start(); //启动100个线程用来在文件中搜索指定的关键字 for (int i = 1; i 《= SEARCH_THREADS; i++) new Thread(new SearchTask(queue, keyword)).start(); } } class FileEnumerationTask implements Runnable { //哑元文件对象，放在阻塞队列最后，用来标示文件已被遍历完 public static File DUMMY = new File(““); private BlockingQueue《File》 queue; private File startingDirectory; public FileEnumerationTask(BlockingQueue《File》 queue, File startingDirectory) { this.queue = queue; this.startingDirectory = startingDirectory; } public void run() { try { enumerate(startingDirectory); queue.put(DUMMY);//执行到这里说明指定的目录下文件已被遍历完 } catch (InterruptedException e) { } } // 将指定目录下的所有文件以File对象的形式放入阻塞队列中 public void enumerate(File directory) throws InterruptedException { File files = directory.listFiles(); for (File file : files) { if (file.isDirectory()) enumerate(file); else //将元素放入队尾，如果队列满，则阻塞 queue.put(file); } } } class SearchTask implements Runnable { private BlockingQueue《File》 queue; private String keyword; public SearchTask(BlockingQueue《File》 queue, String keyword) { this.queue = queue; this.keyword = keyword; } public void run() { try { boolean done = false; while (!done) { //取出队首元素，如果队列为空，则阻塞 File file = queue.take(); if (file == FileEnumerationTask.DUMMY) { //取出来后重新放入，好让其他线程读到它时也很快的结束 queue.put(file); done = true; } else search(file); } } catch (IOException e) { e.printStackTrace(); } catch (InterruptedException e) { } } public void search(File file) throws IOException { Scanner in = new Scanner(new FileInputStream(file)); int lineNumber = 0; while (in.hasNextLine()) { lineNumber++; String line = in.nextLine(); if (line.contains(keyword)) System.out.printf(“%s:%d:%s%n“, file.getPath(), lineNumber, line); } in.close(); } }

PriorityQueue使用求助

从大到小：priority_queue: 默认9 6 5 3 2由小到大：priority_queue《int, vector《int》, greater《int》 》2 3 5 6 9;由大到小：struct node{ friend bool operator《 (node n1, node n2) { return n1.priority 《 n2.priority; } int priority; int value;};9 6 5 3 2priority_queue《int》 que;que.push();que.top();que.pop();); printf(“采用默认优先关系:\n(priority_queue《int》que;)\n“); printf(“Queue 0:\n“); while(!que.empty()) { printf(“%3d“,que.top()); que.pop(); } puts(““); puts(““); printf(“采用结构体自定义优先级方式一:\n(priority_queue《int,vector《int》,cmp》que;)\n“); printf(“Queue 1:\n“); while(!que1.empty()) { printf(“%3d“,que1.top()); que1.pop(); } puts(““); printf(“Queue 2:\n“); while(!que2.empty()) { printf(“%3d“,que2.top()); que2.pop(); } puts(““); puts(““); printf(“采用头文件\“functional\“内定义优先级：\n(priority_queue《int, vector《int》,greater《int》/less《int》 》que;)\n“); printf(“Queue 3:\n“); while(!que3.empty()) { printf(“%3d“,que3.top()); que3.pop(); } puts(““); printf(“Queue 4 :\n“); while(!que4.empty()) { printf(“%3d“,que4.top()); que4.pop(); } puts(““); puts(““); printf(“采用结构体自定义优先级方式二:\n(priority_queue《number》que)\n“); printf(“Queue 5:\n“); while(!que5.empty()) { printf(“%3d“,que5.top()); que5.pop(); } puts(““); printf(“Queue 6:\n“); while(!que6.empty()) { printf(“%3d“,que6.top()); que6.pop(); } system(“pause“); return 0; }