优先队列的背景

less flexibility, more speed

如果我们的目的是找到最小的值，比较其他数据结构：

  • Lists
    • If sorted: FindMin is O(1) but Insert is O(N)
    • If not sorted: Insert is O(1) but FindMin is O(N)
  • Balanced Binary Search Trees (BSTs)
    • Insert is O(log N) and FindMin is O(log N)
  • Hash Tables
    • Insert O(1) but no hope for FindMin
  • BSTs look good but…
    • BSTs are efficient for all Finds, not just FindMin
    • We only need FindMin

PQ 优先队列

Useful if you want to keep track of the “smallest”, “largest”, “best” etc. seen so far.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/** (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();
}

  • getSmallest()
    return the item in the root node.
  • add(x)
    place the new employee in the last position, and promote as high as possible.
  • removeSmallest()
    assassinate the president (of the company), promote the rightmost person in the company to president. Then demote repeatedly, always taking the ‘better’ successor.

binary heaps 二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。适合用来实现优先队列。

复杂度

Space needed for heap of N nodes:

  • O(MaxN)
  • An array of size MaxN, plus a variable to store the size N

    Time

  • FindMin: O(1)
  • DeleteMin and Insert: O(log N)
  • BuildHeap from N inputs : O(N)

BuildHeap

The binary heap is sometimes constructed from an initial collection of items  can be done with N successive inserts.(O(N) average but O(N logN) worst-case)

简单描述一下这个方法就是：先按照输入的顺序建立起一个二叉结构，然后从中间位置的结点开始向上渗透到顶，使得每个结点都满足堆的性质。