Java优先队列(PriorityQueue)实现重写compare操作

发布时间：2020-10-29 15:15:11 作者：Leah
来源：亿速云阅读：831

这篇文章将为大家详细讲解有关Java优先队列(PriorityQueue)实现重写compare操作，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

package myapp.kit.quickstart.utils;
 
import java.util.Comparator;
import java.util.Queue;
 
/**
 * priority queue (heap) demo.
 *
 * @author huangdingsheng
 * @version 1.0, 2020/5/8
 */
public class PriorityQueue { 
 
  public static void main(String[] args) {
 
    // min heap, process custom data struct
    Queue<Node> minHeap = new java.util.PriorityQueue<>(new Comparator<Node>(){
      @Override
      public int compare(Node o1, Node o2) {
        return o1.v - o2.v;
      }
    }); 
 
    // do sth...
    minHeap.add(new Node(1, 2));
    minHeap.add(new Node(2, 9)); 
  }
 
  // custom data struct
  static class Node {
    int k;
    int v;
    public Node(int k, int v) {
      this.k = k;
      this.v = v;
    }
  } 
}

补充知识：Java中PriorityQueue的排序，堆排序

PrioriryQueue是Queue接口的一个队列实现类，但它的排序并不是典型的队列式先进先出（FIFO）的方式。

PriorityQueue的排序方式分为两种，一种是自然排序，这是按照加入元素的大小从小到大排序的。第二种是定制排序，是使用comparator类来重写compare(Object o1,Object o2)方法来实现定制排序的。但是这些都不是关键，关键在于PriorityQueue的排序不是普通的排序，而是堆排序，这有什么不同呢？来看下面一段代码：

import java.util.PriorityQueue;
public class PriorityQueueTest3 
{
 public static void main(String[] args) 
 {
 PriorityQueue pq = new PriorityQueue();
 pq.offer(6);
 pq.offer(-3);
 pq.offer(0);
 pq.offer(9);
 System.out.println(pq);
 }
}

输出结果：[-3,6,0,9]

不是说是按从小到大来排序的吗？怎么没排序？

原因是堆排序只会保证第一个元素也就是根节点的元素是当前优先队列里最小（或者最大）的元素，而且每一次变化之后，比如offer()或者poll()之后，都会进行堆重排，所以如果想要按从小到大的顺序取出元素，那么需要用一个for循环，如下：

import java.util.PriorityQueue;
public class PriorityQueueTest3 
{
 public static void main(String[] args) 
 {
 PriorityQueue pq = new PriorityQueue();
 pq.offer(6);
 pq.offer(-3);
 pq.offer(0);
 pq.offer(9);
 int len = pq.size();//这里之所以取出.size()大小，因为每一次poll()之后size大小都会变化，所以不能作为for循环的判断条件
 for(int i=0;i<len;i++){
  System.out.print(pq.poll()+" ");
 }
 System.out.println();
 }
}

输出 -3 0 6 9，按照从小到大的顺序输出的

关于Java优先队列(PriorityQueue)实现重写compare操作就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。

Java优先队列(PriorityQueue)实现重写compare操作

相关阅读