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

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

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

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(); //迭代器

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;
              }
          });
          }
      }
  }

参考：

1. 官方文档：PriorityQueue (Java Platform SE 8 )
2. Java 优先队列（PriorityQueue）总结_lee的Csdn的博客-CSDN博客_java 优先队列
3. Java优先级队列(堆)及对象的比较_来学习的小张的博客-CSDN博客_java 优先队列 比较
4. Java优先队列/堆（PriorityQueue）中3种重写compare的方法_hellosc01的博客-CSDN博客_优先队列重写