第6章 优先队列（堆）

 1 public class BinaryHeap<AnyType extends Comparable<? super AnyType>>
 2 {
 3     public BinaryHeap(){ this(DEFAULT_CAPACITY); }
 4     public BinaryHeap(int capacity)
 5     {
 6         currentSize = 0;
 7         array = (AnyType [])new Comparable[capacity + 1];
 8     }
 9     
10     public BinaryHeap(AnyType[] items)
11     {
12         currentSize = items.length;
13         array = (AnyType[])new Comparable[(currentSize + 2) * 11 / 10];
14         
15         int i = 1;
16         for (AnyType item : items)
17             array[i++] = item;
18         buildHeap();
19     }
20     
21     public void insert(AnyType x)
22     {
23         if (currentSize == array.length - 1)
24             enlargeArray(array.length * 2 + 1);
25         
26         int hole = ++currentSize;
27         for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2)
28             array[hole] = array[hole / 2];
29         array[hole] = x;
30     }
31     
32     private void enlargeArray(int newSize)
33     {
34         AnyType[] old = array;
35         array = (AnyType[])new Comparable[newSize];
36         for (int i = 0; i < old.length; i++)
37             array[i] = old[i];
38     }
39     
40     public AnyType findMin()
41     {
42         if (isEmpty())
43             throw new UnderflowException();
44         return array[1];
45     }
46     
47     public AnyType deleteMin()
48     {
49         if (isEmpty())
50             throw new UnderflowException();
51         AnyType minItem = findMin();
52         array[1] = array[currentSize--];
53         percolateDown(1);
54         
55         return minItem;
56     }    
57     
58     private void buildHeap()
59     {
60         for (int i = currentSize / 2; i > 0; i--)
61             percolateDown(i);
62     }
63     
64     public boolean isEmpty(){ return currentSize == 0; }
65     
66     public void makeEmpty(){ currentSize = 0; }
67     
68     private static final int DEFAULT_CAPACITY = 10;
69     
70     private int currentSize;
71     private AnyType[] array;
72     
73     private void percolateDown(int hole)
74     {
75         int child;
76         AnyType tmp = array[hole];
77         for (; hole * 2 <= currentSize; hole = child)
78         {
79             child = hole * 2;
80             if (child != child && array[child + 1].compareTo(array[child]) < 0)
81                 child++;
82             if (array[child].compareTo(tmp) < 0)
83                 array[hole] = array[child];
84             else 
85                 break;
86         }
87         array[hole] = tmp;
88     }
89 }