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

Java优先队列(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 minHeap = new java.util.PriorityQueue<>(new Comparator(){

@Override

public int compahttp://re(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

System.out.print(pq.poll()+" ");

}

System.out.println();

}

}

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

System.out.print(pq.poll()+" ");

}

System.out.println();

}

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。