Java教程

【Java数据结构及算法实战】系列011:数组实现的优先级队列PriorityQueue

本文主要是介绍【Java数据结构及算法实战】系列011:数组实现的优先级队列PriorityQueue,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

PriorityQueue是基于数组实现的无界优先级队列。PriorityQueue中的元素按其自然顺序排序,或由队列构造时提供的比较器根据所使用的构造函数排序。优先级队列不允许空元素,依赖自然顺序的优先级队列也不允许插入不可比较的对象。




PriorityQueue本质上就是一个最小堆存储结构数组,通过“极大优先级堆”实现的,即堆顶元素是优先级最大的元素。堆的操作,主要就是两个:siftUp(向上调整堆)和siftDown(向下调整堆)。






PriorityQueue的队首是相对于指定顺序来说优先级的值最小的元素。如果多个元素优先级的值都是最小,那么头部就是其中一个元素。PriorityQueue的检索操作poll、remove和peek等都是访问位于队首的元素。




PriorityQueue是无界队列,因此插入的元素是无限制的,但其具有一个内部容量,它控制用于在队列上存储元素的数组的大小。它总是至少和队列一样大。当元素被添加到优先级队列时,其容量会自动增长。




PriorityQueue及其迭代器实现了Collection和Iterator接口的所有可选方法。方法itilerator()提供的迭代器和方法spliterator()提供的分离器并不保证以任何特定的顺序遍历优先级队列的元素。如果需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).。




注意PriorityQueue是唯一一个非线程安全的队列实现类,适合用于单线程存放数据并且将数据排序。如果是在多个线程中有修改了队列的场景,那么不应该用线程PriorityQueue,而应该使用线程安全的java.util.concurrent.PriorityBlockingQueue类。




PriorityQueue是Java Collections Framework的一个成员。






1.   PriorityQueue的声明


PriorityQueue的接口和继承关系如下




public class PriorityQueue<E> extends AbstractQueue<E>


   implements java.io.Serializable {


  …


}






完整的接口继承关系如下图所示。


https://img2.sycdn.imooc.com/626f309d0001720b02910188.jpg










从上述代码可以看出,PriorityQueue既实现了java.io.Serializable接口,又继承了java.util.AbstractQueue<E>。








2.   PriorityQueue的成员变量和构造函数






以下是PriorityQueue的构造函数和成员变量。




// 默认数组容量


   private static final int DEFAULT_INITIAL_CAPACITY = 11;


 


// 元素数组


   transient Object[] queue;


 


// 队列中的元素个数


   int size;




   // 比较器


   private final Comparator<? super E> comparator;




   // 结构性修改的次数


   transient int modCount;




   public PriorityQueue() {


       this(DEFAULT_INITIAL_CAPACITY, null);


   }




   public PriorityQueue(int initialCapacity) {


       this(initialCapacity, null);


   }




   public PriorityQueue(Comparator<? super E> comparator) {


       this(DEFAULT_INITIAL_CAPACITY, comparator);


   }




   public PriorityQueue(int initialCapacity,


                        Comparator<? super E> comparator) {


       if (initialCapacity < 1)


           throw new IllegalArgumentException();


       this.queue = new Object[initialCapacity];


       this.comparator = comparator;


   }




   public PriorityQueue(Collection<? extends E> c) {


       if (c instanceof SortedSet<?>) {


           SortedSet<? extends E> ss = (SortedSet<? extends E>) c;


           this.comparator = (Comparator<? super E>) ss.comparator();


           initElementsFromCollection(ss);


       }


       else if (c instanceof PriorityQueue<?>) {


           PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;


           this.comparator = (Comparator<? super E>) pq.comparator();


           initFromPriorityQueue(pq);


       }


       else {


           this.comparator = null;


           initFromCollection(c);


       }


   }




   public PriorityQueue(PriorityQueue<? extends E> c) {


       this.comparator = (Comparator<? super E>) c.comparator();


       initFromPriorityQueue(c);


   }




   public PriorityQueue(SortedSet<? extends E> c) {


       this.comparator = (Comparator<? super E>) c.comparator();


       initElementsFromCollection(c);


   }






从上述代码可以看出,构造函数有6种。构造函数中的参数含义如下




l  initialCapacity用于设置队列中内部数组的容量。如果没有指定,则会使用默认数组容量DEFAULT_INITIAL_CAPACITY的值。


l  comparator为比较器


l  c用于设置最初包含给定集合的元素,按集合迭代器的遍历顺序添加




类成员queue是一个数组,用于存储队列中的元素。size用于记录队列中的元素个数。




modCount主要用于记录PriorityQueue被结构性修改的次数,比如像offer、clear、poll等操作的时候,modCount都会自增。


3.   PriorityQueue的核心方法


以下对PriorityQueue常用核心方法的实现原理进行解释。






3.1.     offer(e)


执行offer(e)方法后有两种结果




l  队列未达到容量时,返回 true


l  队列达到容量时,先扩容,再返回 true




PriorityQueue的offer (e)方法源码如下:




public boolean offer(E e) {


       if (e == null)    // 判空


           throw new NullPointerException();


       modCount++;


       int i = size;


       if (i >= queue.length)


           grow(i + 1);  // 扩容


       siftUp(i, e);  // 插入数据


       size = i + 1;


       return true;


   }




从上面代码可以看出,执行offer(e)方法时,分为以下几个步骤:




l  判断待入队的元素e是否为null。为null则抛出NullPointerException异常。


l  判断当前队列中的元素是否已经大于等于队列的容量,如果是则证明队列已经满了,需要先通过grow ()方法扩容。


l  通过siftUp()方法插入数据元素


l  返回true。




grow()方法源码如下:






private void grow(int minCapacity) {


       int oldCapacity = queue.length;


       int newCapacity = ArraysSupport.newLength(oldCapacity,


               minCapacity - oldCapacity,


               oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1


               );


       queue = Arrays.copyOf(queue, newCapacity);


}




siftUp()方法源码如下:




private void siftUp(int k, E x) {


       if (comparator != null)


           siftUpUsingComparator(k, x, queue, comparator);


       else


           siftUpComparable(k, x, queue);


   }




   private static <T> void siftUpComparable(int k, T x, Object[] es) {


       Comparable<? super T> key = (Comparable<? super T>) x;


       while (k > 0) {


           int parent = (k - 1) >>> 1;


           Object e = es[parent];


           if (key.compareTo((T) e) >= 0)


               break;


           es[k] = e;


           k = parent;


       }


       es[k] = key;


   }




   private static <T> void siftUpUsingComparator(


       int k, T x, Object[] es, Comparator<? super T> cmp) {


       while (k > 0) {


           int parent = (k - 1) >>> 1;


           Object e = es[parent];


           if (cmp.compare(x, (T) e) >= 0)


               break;


           es[k] = e;


           k = parent;


       }


       es[k] = x;


}






在上述代码中,在位置k处插入项x,通过向上提升x到树形结构中来维护堆的不变性,直到x大于或等于它的父节点或根节点。


3.2.     add(e)


执行add(e)方法后有有两种结果




l  队列未达到容量时,返回 true


l  队列达到容量时,先扩容,再返回 true




PriorityQueue的add(e)方法源码如下:




   public boolean add(E e) {


       return offer(e);


   }




从上面代码可以看出,add(e)方法等同于offer(e)方法的实现。









3.3.     poll ()


执行poll()方法后有两种结果:




l  队列不为空时,返回队首值并移除


l  队列为空时,返回 null






PriorityQueue的poll()方法源码如下:




public E poll() {


       final Object[] es;


       final E result;




       if ((result = (E) ((es = queue)[0])) != null) {


           modCount++;


           final int n;


           final E x = (E) es[(n = --size)];


           es[n] = null;


           if (n > 0) {


               final Comparator<? super E> cmp;


               if ((cmp = comparator) == null)


                   siftDownComparable(0, x, es, n);


               else


                   siftDownUsingComparator(0, x, es, n, cmp);


           }


       }


       return result;


}




从上面代码可以看出,执行poll()方法时,分为以下几个步骤:




l  先取队列的队首元素。


l  如果队首元素不存在,直接返回null。


l  如果队首元素存在,则返回该元素同时通过siftDownComparable() 或者siftDownUsingComparator()方法来移除元素。




siftDownComparable()和siftDownUsingComparator()方法源码如下:






 


private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {


       Comparable<? super T> key = (Comparable<? super T>)x;


       int half = n >>> 1;


       while (k < half) {


           int child = (k << 1) + 1;


           Object c = es[child];


           int right = child + 1;


           if (right < n &&


               ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)


               c = es[child = right];


           if (key.compareTo((T) c) <= 0)


               break;


           es[k] = c;


           k = child;


       }


       es[k] = key;


   }




   private static <T> void siftDownUsingComparator(


       int k, T x, Object[] es, int n, Comparator<? super T> cmp) {


       int half = n >>> 1;


       while (k < half) {


           int child = (k << 1) + 1;


           Object c = es[child];


           int right = child + 1;


           if (right < n && cmp.compare((T) c, (T) es[right]) > 0)


               c = es[child = right];


           if (cmp.compare(x, (T) c) <= 0)


               break;


           es[k] = c;


           k = child;


       }


       es[k] = x;


   }




3.4.     remove()


执行remove()方法后有两种结果:




l  队列不为空时,返回队首值并移除


l  队列为空时,抛出异常




PriorityQueue的remove()方法其实是调用了父类AbstractQueue的remove ()方法,源码如下:




public E remove() {


       E x = poll();


       if (x != null)


           return x;


       else


           throw new NoSuchElementException();


}




从上面代码可以看出,remove()直接调用了poll()方法。如果poll()方法返回结果为null,则抛出NoSuchElementException异常。




poll()方法此处不再赘述。








3.5.     peek()


执行peek()方法后有两种结果:




l  队列不为空时,返回队首值但不移除


l  队列为空时,返回null






peek()方法源码如下:




public E peek() {


       return (E) queue[0];


}




从上面代码可以看出,peek()方法比较简单,直接就是获取了数组里面的索引为0的元素。




3.6.     element()


执行element()方法后有两种结果:




l  队列不为空时,返回队首值但不移除


l  队列为空时,抛出异常






element()方法其实是调用了父类AbstractQueue的element()方法,源码如下:




public E element() {


       E x = peek();


       if (x != null)


           return x;


       else


           throw new NoSuchElementException();


}




从上面代码可以看出,执行element()方法时,先是获取peek()方法的结果,如果结果是null,则抛出NoSuchElementException异常。






4.   PriorityQueue的单元测试




PriorityQueue的单元测试如下:








package com.waylau.java.demo.datastructure;




import static org.junit.jupiter.api.Assertions.assertEquals;


import static org.junit.jupiter.api.Assertions.assertNull;


import static org.junit.jupiter.api.Assertions.assertThrows;


import static org.junit.jupiter.api.Assertions.assertTrue;




import java.util.NoSuchElementException;


import java.util.PriorityQueue;


import java.util.Queue;




import org.junit.jupiter.api.Test;




/**


* PriorityQueue Tests


*


* @since 1.0.0 2020年5月24日


* @author <a href="https://waylau.com">Way Lau</a>


*/


class PriorityQueueTests {


   @Test


   void testOffer() {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列未满时,返回 true


       boolean resultNotFull = queue.offer("Java");


       assertTrue(resultNotFull);




       // 测试队列达到容量时,会自动扩容


       queue.offer("C");


       queue.offer("Python");


       boolean resultFull = queue.offer("C++"); // 扩容


       assertTrue(resultFull);


   }




@Test


   void testAdd() {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列未满时,返回 true


       boolean resultNotFull = queue.add("Java");


       assertTrue(resultNotFull);




       // 测试队列满则扩容,返回 true


       queue.add("C");


       queue.add("Python");


       boolean resultFull = queue.add("C++"); // 扩容


       assertTrue(resultFull);


}




   @Test


   void testPoll() throws InterruptedException {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列为空时,返回 null


       String resultEmpty = queue.poll();


       assertNull(resultEmpty);




       // 测试队列不为空时,返回队首值并移除


       queue.add("Java");


       queue.add("C");


       queue.add("Python");


       String resultNotEmpty = queue.poll();


       assertEquals("C", resultNotEmpty);


   }




   @Test


   void testRemove() throws InterruptedException {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列为空时,抛出异常


       Throwable excpetion = assertThrows(NoSuchElementException.class, () -> {


           queue.remove();// 抛异常


       });




       assertEquals(null, excpetion.getMessage());




       // 测试队列不为空时,返回队首值并移除


       queue.add("Java");


       queue.add("C");


       queue.add("Python");


       String resultNotEmpty = queue.remove();


       assertEquals("C", resultNotEmpty);


   }




   @Test


   void testPeek() throws InterruptedException {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列不为空时,返回队首值并但不移除


       queue.add("Java");


       queue.add("C");


       queue.add("Python");


       String resultNotEmpty = queue.peek();


       assertEquals("C", resultNotEmpty);


       resultNotEmpty = queue.peek();


       assertEquals("C", resultNotEmpty);


       resultNotEmpty = queue.peek();


       assertEquals("C", resultNotEmpty);




       // 测试队列为空时,返回null


       queue.clear();


       String resultEmpty = queue.peek();


       assertNull(resultEmpty);


   }




   @Test


   void testElement() throws InterruptedException {


       // 初始化队列


       Queue<String> queue = new PriorityQueue<String>(3);




       // 测试队列不为空时,返回队首值并但不移除


       queue.add("Java");


       queue.add("C");


       queue.add("Python");


       String resultNotEmpty = queue.element();


       assertEquals("C", resultNotEmpty);


       resultNotEmpty = queue.element();


       assertEquals("C", resultNotEmpty);


       resultNotEmpty = queue.element();


       assertEquals("C", resultNotEmpty);




       // 测试队列为空时,抛出异常


       queue.clear();


       Throwable excpetion = assertThrows(NoSuchElementException.class, () -> {


           queue.element();// 抛异常


       });




       assertEquals(null, excpetion.getMessage());


   }


}




5.   PriorityQueue的应用案例:英雄战力排行榜


以下是一个英雄战力排行榜的示例。该示例模拟了6个英雄,可以根据英雄的战力由高至低排序。




以下是Hero类,用来代表英雄:






package com.waylau.java.demo.datastructure;






/**


* Hero


*


* @since 1.0.0 2020年5月23日


* @author <a href="https://waylau.com">Way Lau</a>


*/


public class Hero {




   private String name;


 


   private Integer power; // 战力


 


   public Hero(String name, Integer power) {


       this.name = name;


       this.power = power;


   }


 


   public String getName() {


       return name;


   }




   public void setName(String name) {


       this.name = name;


   }




   public Integer getPower() {


       return power;


   }




   public void setPower(Integer power) {


       this.power = power;


   }




   @Override


   public String toString() {


       return "Hero [name=" + name + ", power=" + power + "]";


   }




}






以下是应用主程序:










package com.waylau.java.demo.datastructure;




import java.util.Comparator;


import java.util.PriorityQueue;


import java.util.Queue;




/**


* PriorityQueue Demo


*


* @since 1.0.0 2020年5月24日


* @author <a href="https://waylau.com">Way Lau</a>


*/


public class PriorityQueueDemo {


   public static void main(String[] args) {


       int n = 6;


     


       Queue<Hero> queue = new PriorityQueue<Hero>(n, new Comparator<Hero>() {


           // 战力由大到小排序


           @Override


           public int compare(Hero hero0, Hero hero1) {


               return hero1.getPower().compareTo(hero0.getPower());


           }


       });




       queue.add(new Hero("Nemesis", 95));


       queue.add(new Hero("Edifice Rex", 88));


       queue.add(new Hero("Marquis of Death", 91));


       queue.add(new Hero("Magneto", 96));


       queue.add(new Hero("Hulk", 85));


       queue.add(new Hero("Doctor Strange", 94));




     


       for (int i = 0; i<n ; i++) {


           System.out.println(queue.poll());


       }


   }




}










运行上述程序,输出内容如下:




Hero [name=Magneto, power=96]


Hero [name=Nemesis, power=95]


Hero [name=Doctor Strange, power=94]


Hero [name=Marquis of Death, power=91]


Hero [name=Edifice Rex, power=88]


Hero [name=Hulk, power=85]


6.   参考引用


本系列归档至《Java数据结构及算法实战》:https://github.com/waylau/java-data-structures-and-algorithms-in-action

《数据结构和算法基础(Java语言实现)》(柳伟卫著,北京大学出版社出版):https://item.jd.com/13014179.html



这篇关于【Java数据结构及算法实战】系列011:数组实现的优先级队列PriorityQueue的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!