13.1.优先队列接口

发表于 更新于 分类于 ， 阅读次数： 本文字数： 392 阅读时长 ≈ 1 分钟

\(13.1\)优先队列接口

1.优先队列的引入

  我们知道\(BST\)可以实现数据的快速搜索，那么如果我们只关心对最大(最小)元素的查找呢？

  这时，我们就可以引入优先队列(\(Priority\;Queue\))的\(ADT\)。在优先队列中，我们只能对一组数据中的最小元素进行操作：

1
2
3
4
5
6
7
8
9
10
11
12
/** (Min) Priority Queue: Allowing tracking and removal of 
  * the smallest item in a priority queue. */
public interface MinPQ<Item> {
    /** Adds the item to the priority queue. */
    public void add(Item x);
    /** Returns the smallest item in the priority queue. */
    public Item getSmallest();
    /** Removes the smallest item from the priority queue. */
    public Item removeSmallest();
    /** Returns the size of the priority queue. */
    public int size();
}

2.优先队列的实现

  假如我们用链表实现以下的问题：

  \(question:\)

  • Consider the scenario where we are monitoring text messages between citizens and want to keep track of unharmonious conversations.
  • Each day, you prepare a report of \(M\) messages that are the most unharmonious using a HarmoniousnessComparator.

  用链表将得到如下实现： 

1
2
3
4
5
6
7
8
9
10
public List<String> unharmoniousTexts(Sniffer sniffer, int M) {
    ArrayList<String>allMessages = new ArrayList<String>();
    for (Timer timer = new Timer(); timer.hours() < 24; ) {
        allMessages.add(sniffer.getNextMessage());
    }

    Comparator<String> cmptr = new HarmoniousnessComparator();
    Collections.sort(allMessages, cmptr, Collections.reverseOrder());

    return allMessages.sublist(0, M);

  然而，这种方式的弊端为：我们只需要\(\Theta(M)\)空间内的变量，但该方法使用了\(\Theta(N)\)的空间。

  为了优化内存的占用，我们可以尝试用下面的数据结构实现优先队列：

  • Ordered Array
    • add:\(\Theta(N)\)
    • getSmallest:\(\Theta(1)\)
    • removeSmallest:\(\Theta(N)\)
  • Bushy BST
    • add:\(\Theta(\log N)\)
    • getSmallest:\(\Theta(\log N)\)
    • removeSmallest:\(\Theta(\log N)\)
  • HashTable
    • add:\(\Theta(1)\)
    • getSmallest:\(\Theta(N)\)
    • removeSmallest:\(\Theta(N)\)

  那么，我们有更优秀的实现方法吗？