Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Mandate<Key extends Comparable<Key>> {
- private Key[] pq; // heap-ordered complete binary tree
- private int N = 0; // in pq[1..N] with pq[0] unused
- public Mandate(int maxN) { pq = (Key[]) new Comparable[maxN+1];
- }
- public boolean isEmpty() {
- return N == 0;
- }
- public int size() {
- return N;
- }
- public void insert(Key v) {
- pq[++N] = v;
- swim(N);
- }
- public Key delMax() {
- Key max = pq[1];
- exch(1, N--);
- pq[N+1] = null;
- sink(1);
- return max;
- }
- private boolean less(int i, int j) {
- return pq[i].compareTo(pq[j]) < 0;
- }
- private void exch(int i, int j) {
- Key t = pq[i]; pq[i] = pq[j]; pq[j] = t;
- }
- private void swim(int k) {
- while (k > 1 && less(k/2, k)) {
- exch(k/2, k);
- k = k/2;
- }
- }
- private void sink(int k) {
- while (2*k <= N) {
- int j = 2*k;
- if (j < N && less(j, j+1)) j++;
- if (!less(k, j)) break;
- exch(k, j);
- k = j;
- }
- }
- public static void main(String[] args) {
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement