堆做为优先级队列的实现

1. public class Heap {
2.  
3.     private static final int DEFAULT_SIZE = 10;
4.     private int[] array;
5.     private int tail;
6.     
7.     public Heap() {
8.         array = new int[DEFAULT_SIZE];
9.         tail = -1;
10.     }
11.  
12.     public Heap(int initialSize) {
13.         array = new int[initialSize];
14.         tail = -1;
15.     }
16.  
17.     /**
18.     *    Construct a heap using existing data
19.     *
20.     *    @param data        the existing data
21.     *    @param method    1 for John.Williams 2 for Robert.Floyd
22.     **/
23.     public Heap(int[] data, int method) {
24.         this(data.length);
25.         switch (method) {
26.             case 1:
27.                 constructHeapWilliams(data);
28.                 break;
29.             case 2:
30.                 constructHeapFloyd(data);
31.                 break;
32.             default:
33.                 throw new RuntimeException("Bad param method: method thould be 1 or 2");
34.         }
35.     }
36.  
37.     private void constructHeapWilliams(int[] data) {
38.         for (int i : data) {
39.             this.heapEnqueue(i);
40.         }
41.     }
42.  
43.     private void constructHeapFloyd(int[] data) {
44.         System.arraycopy(data, 0, this.array, 0, data.length);
45.         int lastBranch = this.array.length/2 - 1;
46.         for (int i = lastBranch; i >= 0; i--) {
47.             moveDown(this.array, i, this.array.length - 1);
48.         }
49.         tail = data.length - 1;
50.     }
51.     
52.     private void moveDown(int[] data, int first, int last) {
53.         int larger = 2 * first + 1;
54.         while (larger <= last) {
55.             if (larger < last && data[larger] < data[larger + 1]) {    //find the larger child
56.                 larger++;
57.             }
58.             if (data[first] < data[larger]) {    //move down on larger child
59.                 // swap 
60.                 int temp = array[first];    
61.                 array[first] = array[larger];
62.                 array[larger] = temp;
63.  
64.                 first = larger;
65.                 larger = 2 * first + 1;        
66.             } else {
67.                 larger = last + 1;                //exit the while loop
68.             }
69.         }
70.     }
71.     private void reAllocateHeap() {
72.         int[] tmp = new int[2 * array.length];
73.         System.arraycopy(array, 0, tmp, 0, tail + 1);
74.         array = tmp;
75.     }
76.     
77.     public boolean isEmpty() {
78.         return tail == -1;
79.     }
80.     
81.     public void heapEnqueue(int el) {
82.         if (tail + 1 == array.length) {
83.             this.reAllocateHeap();
84.         }
85.         array[++tail] = el;
86.         int i = tail;
87.         int j = (i - 1)/2;
88.         while (i != 0 && el > array[j]) {
89.             // swap el and its parent
90.             int temp = array[j];    
91.             array[j] = array[i];
92.             array[i] = temp;
93.  
94.             i = j;
95.             j = (i - 1)/2;
96.         }
97.     }
98.  
99.     public int heapDequeue() {
100.         if (tail == -1) {
101.             throw new RuntimeException("there is no element in heap");
102.         }
103.         int el = array[0];
104.         array[0] = array[tail--];
105.         if (tail < 1) {
106.             return el;
107.         }
108.         int lastBranch = (tail - 1)/2;
109.         int i = 0;
110.         int j = 2 * i + 1;
111.         if (j + 1 <= tail) {
112.             if (array[j] < array[j + 1]) {
113.                 j++;
114.             }
115.         }
116.         while (i <= lastBranch && array[i] < array[j]) {
117.             int temp = array[j];    
118.             array[j] = array[i];
119.             array[i] = temp;
120.  
121.             i = j;
122.             j = 2 * i + 1;
123.             if (j + 1 <= tail) {
124.                 if (array[j] < array[j + 1]) {
125.                     j++;
126.                 }
127.             }
128.         }
129.         return el;
130.     }
131.  
132.     public String toString() {
133.         StringBuilder sb = new StringBuilder();
134.         sb.append("[");
135.         for (int i = 0; i < this.tail; i++) {
136.             sb.append(this.array[i] + ",");
137.         }
138.         sb.append(this.array[this.tail] + "]");
139.         return sb.toString();
140.     }
141.  
142.     public boolean equals(Object o) {
143.         if (o instanceof Heap) {
144.             Heap h = (Heap)o;
145.             if (this.tail != h.tail) {
146.                 return false;
147.             }
148.             for (int i = 0; i < this.tail + 1; i++) {
149.                 if (this.array[i] != h.array[i]) {
150.                     return false;
151.                 }
152.             }
153.             return true;
154.         } else {
155.             return false;
156.         }
157.     }
158.  
159.     private static void test() {
160.         Heap heap = new Heap();
161.         for (int i = 0; i < 10; i++) {
162.             heap.heapEnqueue(i);
163.         }
164.         System.out.println(heap.toString());
165.         while (!heap.isEmpty()) {
166.             System.out.println(heap.heapDequeue());
167.         }
168.         int[] data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, };
169.         Heap heap2 = new Heap(data, 1);
170.         System.out.println(heap2.toString());
171.         Heap heap3 = new Heap(data, 2);
172.         System.out.println(heap3.toString());
173.     }
174.  
175.     public static void main(String[] args) {
176.         test();
177.     }
178. }