|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
class PriorityQueue { private int[] pq; // inside array pyramid binary tree private int N = 0; // pq[0] not used public void Display() { foreach (int val in pq) Console.Write(val+" "); } public PriorityQueue(int maxN) { pq = new int[maxN + 1]; } public bool isEmpty() { return N == 0; } public int size() { return N; } public void Enqueue(int el) { pq[++N] = el; swimUp(N); } public int Dequeue() { int max = pq[1]; Swap(1, N--); //pq[N + 1] = null; swimDown(1); return max; } private void Swap(int i,int j) { int temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } private void swimUp(int k) { while ((k > 1) && (pq[k / 2] < pq[k])) { Swap(k/2,k); k = k / 2; } } private void swimDown(int k) { while (2 * k <= N) { int j = 2 * k; if ((j < N) && (j < j + 1)) j++; if (!(k < j)) break; //swap Swap(k,j); k = j; } } } |