Specialized heaps

1static class DaryHeap {
2    private final int d;
3    private int[] a = new int[16];
4    private int size;
5    DaryHeap(int d) { this.d = d; }
6    void add(int x) {
7        if (size == a.length) a = Arrays.copyOf(a, 2 * size);
8        a[size] = x;
9        int i = size++;
10        while (i > 0 && a[(i - 1) / d] > a[i]) {                 // sift-up: one comparison per level
11            int p = (i - 1) / d;
12            int t = a[p]; a[p] = a[i]; a[i] = t;
13            i = p;
14        }
15    }
16    int poll() {
17        int min = a[0];
18        a[0] = a[--size];
19        int i = 0;
20        while (true) {                           // sift-down: up to d comparisons per level
21            int m = i;
22            for (int c = d * i + 1; c < Math.min(size, d * i + 1 + d); c++) if (a[c] < a[m]) m = c;
23            if (m == i) break;
24            int t = a[i]; a[i] = a[m]; a[m] = t;
25            i = m;
26        }
27        return min;
28    }
29    boolean isEmpty() { return size == 0; }
30}

1static class Node {
2    int key, degree;
3    Node child, sibling;
4    Node(int key) { this.key = key; }
5}
6static Node head;                                // roots, in increasing order of degree
7static void link(Node child, Node parent) {      // both trees have the same degree
8    child.sibling = parent.child;
9    parent.child = child;
10    parent.degree++;
11}
12static Node mergeLists(Node a, Node b) {
13    Node dummy = new Node(0), t = dummy;
14    while (a != null && b != null) {
15        if (a.degree <= b.degree) { t.sibling = a; a = a.sibling; } else { t.sibling = b; b = b.sibling; }
16        t = t.sibling;
17    }
18    t.sibling = a != null ? a : b;
19    return dummy.sibling;
20}
21static Node union(Node a, Node b) {              // like adding two binary numbers
22    Node h = mergeLists(a, b);
23    if (h == null) return null;
24    Node prev = null, x = h, next = x.sibling;
25    while (next != null) {
26        if (x.degree != next.degree || (next.sibling != null && next.sibling.degree == x.degree)) { prev = x; x = next; }
27        else if (x.key <= next.key) { x.sibling = next.sibling; link(next, x); }
28        else { if (prev == null) h = next; else prev.sibling = next; link(x, next); x = next; }
29        next = x.sibling;
30    }
31    return h;
32}
33static void insert(int key) { head = union(head, new Node(key)); }
34static int extractMin() {
35    Node best = head, bestPrev = null, prev = null;
36    for (Node x = head; x != null; prev = x, x = x.sibling) if (x.key < best.key) { best = x; bestPrev = prev; }
37    if (bestPrev == null) head = best.sibling; else bestPrev.sibling = best.sibling;
38    Node rev = null, c = best.child;             // the children, reversed into increasing degree order
39    while (c != null) { Node next = c.sibling; c.sibling = rev; rev = c; c = next; }
40    head = union(head, rev);
41    return best.key;
42}

1static class Node {
2    int key, degree;
3    boolean mark;                                // lost a child since it last became a child itself
4    Node parent, child, left = this, right = this;
5    Node(int key) { this.key = key; }
6}
7static Node min;
8static int size;
9static void addRoot(Node x) {                    // splice x into the circular root list next to min
10    x.parent = null; x.mark = false;
11    if (min == null) { x.left = x; x.right = x; min = x; return; }
12    x.left = min; x.right = min.right; min.right.left = x; min.right = x;
13    if (x.key < min.key) min = x;
14}
15static Node insert(int key) { Node x = new Node(key); addRoot(x); size++; return x; }
16
17static int extractMin() {
18    Node z = min;
19    if (z.child != null) {                       // children become roots
20        List<Node> kids = new ArrayList<>();
21        Node c = z.child;
22        do { kids.add(c); c = c.right; } while (c != z.child);
23        for (Node k : kids) addRoot(k);
24    }
25    z.left.right = z.right; z.right.left = z.left;
26    if (z == z.right) min = null;
27    else { min = z.right; consolidate(); }
28    size--;
29    return z.key;
30}
31static void consolidate() {
32    Node[] table = new Node[64];
33    List<Node> roots = new ArrayList<>();
34    Node c = min;
35    do { roots.add(c); c = c.right; } while (c != min);
36    for (Node w : roots) {
37        Node x = w;
38        int d = x.degree;
39        while (table[d] != null) {               // two trees of degree d: link them into one of degree d + 1
40            Node y = table[d];
41            if (y.key < x.key) { Node t = x; x = y; y = t; }
42            link(y, x);
43            table[d++] = null;
44        }
45        table[d] = x;
46    }
47    min = null;
48    for (Node r : table) if (r != null) addRoot(r);
49}
50static void link(Node y, Node x) {               // y becomes a child of x
51    y.parent = x; y.mark = false;
52    if (x.child == null) { x.child = y; y.left = y; y.right = y; }
53    else { y.left = x.child; y.right = x.child.right; x.child.right.left = y; x.child.right = y; }
54    x.degree++;
55}
56static void decreaseKey(Node x, int newKey) {
57    x.key = newKey;
58    Node p = x.parent;
59    if (p != null && x.key < p.key) { cut(x, p); cascadingCut(p); }   // heap order broke: cut x out
60    if (x.key < min.key) min = x;
61}
62static void cut(Node x, Node p) {
63    if (x.right == x) p.child = null;
64    else { x.left.right = x.right; x.right.left = x.left; if (p.child == x) p.child = x.right; }
65    p.degree--;
66    addRoot(x);
67}
68static void cascadingCut(Node y) {
69    Node z = y.parent;
70    if (z == null) return;
71    if (!y.mark) y.mark = true;                  // the first lost child: just mark it
72    else { cut(y, z); cascadingCut(z); }         // the second: cut it too, and continue upward
73}

1static class Node {
2    int key;
3    Node child, sibling;                         // the first child and the next sibling
4    Node(int key) { this.key = key; }
5}
6static Node meld(Node a, Node b) {
7    if (a == null) return b;
8    if (b == null) return a;
9    if (b.key < a.key) { Node t = a; a = b; b = t; }
10    b.sibling = a.child;                         // the larger root becomes the first child of the smaller
11    a.child = b;
12    return a;
13}
14static Node insert(Node root, int key) { return meld(root, new Node(key)); }
15static Node deleteMin(Node root) {               // the root's key was the minimum; returns the new root
16    List<Node> pairs = new ArrayList<>();
17    Node first = root.child;
18    while (first != null) {                      // pass 1: meld the children in pairs, left to right
19        Node a = first, b = a.sibling;
20        Node next = b == null ? null : b.sibling;
21        a.sibling = null;
22        if (b != null) b.sibling = null;
23        pairs.add(meld(a, b));
24        first = next;
25    }
26    Node result = null;
27    for (int i = pairs.size() - 1; i >= 0; i--) result = meld(pairs.get(i), result);   // pass 2: right to left
28    return result;
29}

1static class IndexedMinPQ {
2    private int n;                               // number of items in the queue
3    private final int[] pq, qp, key;             // pq: heap of item indexes (1-based), qp[i]: position of item i or -1
4    IndexedMinPQ(int capacity) {
5        pq = new int[capacity + 1]; qp = new int[capacity]; key = new int[capacity];
6        Arrays.fill(qp, -1);
7    }
8    boolean contains(int i) { return qp[i] != -1; }
9    void insert(int i, int k) { key[i] = k; pq[++n] = i; qp[i] = n; swim(n); }
10    void decreaseKey(int i, int k) { key[i] = k; swim(qp[i]); }
11    int delMin() {                               // returns the index of the smallest key
12        int min = pq[1];
13        swap(1, n--);
14        sink(1);
15        qp[min] = -1;
16        return min;
17    }
18    int minKey() { return key[pq[1]]; }
19    boolean isEmpty() { return n == 0; }
20    private void swim(int p) { while (p > 1 && key[pq[p / 2]] > key[pq[p]]) { swap(p, p / 2); p /= 2; } }
21    private void sink(int p) {
22        while (2 * p <= n) {
23            int c = 2 * p;
24            if (c < n && key[pq[c + 1]] < key[pq[c]]) c++;
25            if (key[pq[p]] <= key[pq[c]]) break;
26            swap(p, c);
27            p = c;
28        }
29    }
30    private void swap(int x, int y) { int t = pq[x]; pq[x] = pq[y]; pq[y] = t; qp[pq[x]] = x; qp[pq[y]] = y; }
31}