优先队列 | CombinatorX

文章目录

1. 优先队列的一些操作
1. 1.1. 基本操作
2. 优先队列，队列，栈的对比
3. Java与Python下的实现
4. 突然想到的一个问题

优先队列(PriorityQueue) 是一种抽象数据结构，队列内的元素都有对应的优先级，并根据其优先级出队。优先队列一般会使用堆（heap）来实现。

优先队列的一些操作

基本操作

插入一个元素
查看队列第一个（堆顶）元素
取出队列第一个（堆顶）元素

对应的这几个操作的复杂度又是怎样的呢？

操作	复杂度
插入	$O(log^n)$
查看堆顶元素	$O(1)$
取出堆顶元素	$O(log^n)$

优先队列，队列，栈的对比

如果你问优先队列，队列、栈有什么不同之处，那答案简直就是肯定的：

队列：FIFO 先入先出的访问顺序
栈：LIFO 后入先出的访问顺序
优先队列： 根据自定义的估价函数、优先级确定访问顺序

看出来有什么文章么？
首先在形式上，队列和栈貌似是对立的，但是都可以统一在优先队列的这个更加共通的结构下。只是优先队列在估价函数如果使用先入队列的元素具有更高优先级的化就是Queue，如果先入队列的元素具有更低的优先级，那么就是Stack。
所以如果有人说“队列就是栈，栈就是队列”，那么不要怀疑他是不是疯了，其实在这个含义下这句话其实正确的。
再仔细想一下发现好像BFS和DFS的也可以统一起来，因此“BFS就是DFS， DFS就是BFS”在这个语境下也是对的。

Java与Python下的实现

先说说java下的实现，java下有对应的PriorityQueue的数据结构，估价函数可以考虑由实体类实现 Comparable 接口或者是实现一个自定义的Comparator 并在PriorityQueue的构造函数传入，示例代码如下：

PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
priorityQueue.offer(new Node(1)); // O(log(n))
priorityQueue.offer(new Node(2));
Node node = priorityQueue.peek();
Node node = priorityQueue.poll(); // O(log(n))

class Node implements Comparable {
  private int value;
  ......

  @Override
  public int compare(Node other) {
    return other.value - value;
  }
}

下面是Python实现, 由于Python的原生集合没有PriorityQueue的实现，所以我们只有自己寻找办法，事实上我们有两种选择：

使用collections包中的PriorityQueue
使用heapq自己封装

如果使用collections包的实现，那么就需要实体类override cmp 方法来实现估价函数

from collections import PriorityQueue
priorityQueue = PriorityQueue()
priorityQueue.put(Node(1))
priorityQueue.put(Node(2))
node = priorityQueue.get()

class Node(object):
  """docstring for  Node."""
  def __init__(self, value):
    self.val = value

  def __cmp__(self, other):
    return other.val - self.val

突然想到的一个问题

在之前的关于合并k个排序列表的问题上我们又有了新的解法：
原题传送门

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

之前已经有分析到有个时间复杂度为$O(nlog^n)$、空间复杂度$O(1)$的Divided and conquer解法，这里就不按之前的解题方式来做，直接来分析这个优先队列的解决方案。
如果考虑将所有元素全部都扔到这个优先队列，然后再从队列里一个一个取出元素。如果恰巧这个优先队列的估价函数是根据元素的大小进行优先级来排序，元素小的拥有更高的优先级，那么这个想法其实是可行的。
那么来考虑复杂度：

首先是时间复杂度：向优先队列插入一个元素的代价是$O(log^n)$ 那么将所有元素插入的的时间复杂度是$O(nlog^n)$, 接下来的取出元素的操作实际上又遍历了整个列表，因此这部分访问操作的时间复杂度是$O(n)$, 考虑到构建头节点等操作都是常数级的，
因此有整个算法的时间复杂度为 $O(nlog^n + n)$ = $O(nlog^n)$
其次是空间复杂度：由于使用了优先队列的额外空间，因此空间复杂度为$O(n)$

分析完复杂度，下一步就是实现这个算法：

public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        if (lists.length == 1) return lists[0];

        PriorityQueue<ListNode> pqueue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });


        for (ListNode node : lists) {
            if (node != null) {
                pqueue.offer(node);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode node = dummyHead;
        while(!pqueue.isEmpty()) {
            node.next = pqueue.poll();
            node = node.next;
            if (node.next != null) {
                pqueue.offer(node.next);
            }
        }

        return dummyHead.next;
    }

以上的代码其实对长度为1的问题有覆盖，因此可以将这个卫语句去掉，这样代码更简洁些。
因此最后优化的代码是这样的：

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> pqueue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode node1, ListNode node2) {
            return node1.val - node2.val;
        }
    });

    for (ListNode node : lists) {
        if (node != null) {
            pqueue.offer(node);
        }
    }

    ListNode dummyHead = new ListNode(0);
    ListNode node = dummyHead;
    while(!pqueue.isEmpty()) {
        node.next = pqueue.poll();
        node = node.next;
        if (node.next != null) {
            pqueue.offer(node.next);
        }
    }

    return dummyHead.next;
}