GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — programming/problems/priority-queue/MinQueue.java at master · rp-code9/programming Expand file tree/ Copy pathMinQueue.javaMore file actions 70 lines (59 loc) · 1.47 KB / Copy pathMinQueue.javaFile metadata and controls70 lines (59 loc) · 1.47 KB 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 public class MinQueue <Key extends Comparable<Key>> { private int N; private Key[] pq; public MinQueue(int capacity) { pq = (Key[]) new Comparable[capacity + 1]; } public boolean isEmpty() { return N == 0; } public void insert(Key key) { pq[++N] = key; swim(N); } public Key deleteMin() { Key temp = pq[1]; swap(1, N); N--; sink(1); pq[N + 1] = null; return temp; } private void swim(int k) { while (k > 1 && greater(k / 2, k)) { swap(k, k / 2); k = k / 2; } } private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && greater(j, j + 1)) { j = j + 1; } if (!greater(k, j)) { break; } swap(k, j); k = j; } } private boolean greater(int i, int j) { return pq[i].compareTo(pq[j]) > 0; } private void swap(int i, int j) { Key temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } public static void main(String[] args) { String[] names = {"Charlie", "Tom", "Alice", "Hope", "Eve", "Hank", "Bob"}; MinQueue<String> queue = new MinQueue<>(10); for (String s : names) { queue.insert(s); } while(!queue.isEmpty()) { System.out.println(queue.deleteMin()); } } } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |