优先队列(CS61B笔记)

优先队列(以MinPQ为例)

优先队列的接口

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

使用堆（Heap）来实现优先队列

堆

我们定义二进制最小堆满足以下两个属性：

• Min-heap: 每个节点小于等于它的子节点.
• Complete: Missing items only at the bottom level (if any), all nodes are as far left as possible.

在堆中如何满足优先队列所需的操作:

• add: 暂时将节点添加到堆的末尾。然后上游到适当的位置。
  • 上游: 当孩子小于父母时, 交换两者
• getSmallest: 返回堆的根节点
• removeSmallest: 把堆的最后一个节点和根节点互换, 此时删除最后一个节点, 再将根节点下沉到适当位置.
  • 下沉: 当父节点大于子节点时, 交换两者. 在下沉时, 要选择最小的子节点与自身交换以满足Min-heap属性.

我们该如何表示堆中的节点(树结构)?

方法1A: 考虑创建指向子节点的指针, 并将值存储在节点对象内部. These are hardwired links that give us fixed-width nodes.