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

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

public class Tree3<Key> {
    Key[] keys;
    ...

    public void swim(int k) {
        if (keys[parent(k)] ≻ keys[k]) {
        swap(k, parent(k));
        swim(parent(k));              
        }
    }

    public int parent(int k) {
        return (k - 1) / 2;
    } // 观察法