Java优先队列PriorityQueue自定义类的比较_java

最近刷到Leetcode23 合并K个升序链表，这一问题需要用到优先队列PriorityQueue，这里对PriorityQueue的用法进行一些记录：

1. PriorityQueue介绍

Java中PriorityQueue 实现的是Queue 接口，可以使用Queue的方法和自定义方法；其通过完全二叉树构造的小顶堆实现。对于可比较的元素（natural ordering）直接进行比较；对于自定义类的比较，通过构造时传入的比较。

2. 常用方法

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构
public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null
public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator iterator(); //迭代器

3. 自定义类的比较

PriorityQueue采用：Comparble和Comparator两种方式：

Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并重载compareTo方法。

import java.util.Comparator;
import java.util.PriorityQueue;
public class CompTest {
    class Comp implements Comparable {
        int val;
        ListNode ptr;
        Comp(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }
        public int compareTo(Comp b) {
            return this.val - b.val;
        }
    }
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
    }
}

实现Comparator比较器并重载compare方法：

import java.util.Comparator;
import java.util.PriorityQueue;
public class CompTest {
    public static void main(String[] args) {
         PriorityQueue queue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        }
    }
}

参考：