Java優(yōu)先隊列(PriorityQueue)重寫compare操作

更新時間：2020年10月08日 09:38:40 作者：微觀盡頭

這篇文章主要介紹了Java優(yōu)先隊列(PriorityQueue)重寫compare操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

we can custom min heap or max heap by override the method 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;
    }
  } 
}

補(bǔ)充知識：Java中PriorityQueue的排序，堆排序

PrioriryQueue是Queue接口的一個隊列實(shí)現(xiàn)類，但它的排序并不是典型的隊列式先進(jìn)先出（FIFO）的方式。

PriorityQueue的排序方式分為兩種，一種是自然排序，這是按照加入元素的大小從小到大排序的。第二種是定制排序，是使用comparator類來重寫compare(Object o1,Object o2)方法來實(shí)現(xiàn)定制排序的。但是這些都不是關(guān)鍵，關(guān)鍵在于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);
 }
}

輸出結(jié)果：[-3,6,0,9]

不是說是按從小到大來排序的嗎？怎么沒排序？

原因是堆排序只會保證第一個元素也就是根節(jié)點(diǎn)的元素是當(dāng)前優(yōu)先隊列里最?。ɑ蛘咦畲螅┑脑?，而且每一次變化之后，比如offer()或者poll()之后，都會進(jìn)行堆重排，所以如果想要按從小到大的順序取出元素，那么需要用一個for循環(huán)，如下：

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()大小，因?yàn)槊恳淮蝡oll()之后size大小都會變化，所以不能作為for循環(huán)的判斷條件
 for(int i=0;i<len;i++){
  System.out.print(pq.poll()+" ");
 }
 System.out.println();
 }
}

輸出 -3 0 6 9，按照從小到大的順序輸出的

以上這篇Java優(yōu)先隊列(PriorityQueue)重寫compare操作就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: