Priority Queue in Java

Implementation of heap (priority queue) in Java. Nothing fundamentally hard; the idea of visualizing an array to a tree is neat.

import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static class Heap {
        // the logic size of heap
        private int length;
        private int[] arr;

        // assert x in [low, max)
        private static void assert_range(int x, int low, int max) {
            assert (low <= x && x < max);
        }

        private void swap(int i, int j) {
            assert_range(i, 0, length);
            assert_range(j, 0, length);
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        // assuming left and right subtree are max-heap already;
        // O(logN): depth of the tree
        private void maxHeapify(int i) {
            assert_range(i, 0, length);
            var largest = i;
            var left = 2 * i + 1;
            var right = 2 * i + 2;
            if (left < length && arr[left] > arr[largest])
                largest = left;
            if (right < length && arr[right] > arr[largest])
                largest = right;

            if (largest != i) {
                // fix the violation
                swap(i, largest);
                maxHeapify(largest);
            }
        }

        // it seems O(NlogN), but it's actually O(N), since #nodes per level
        // drops exponentially, while the depth grows linearly
        private Heap(int[] arr) {
            length = arr.length;
            this.arr = arr;
            // working bottom-up;
            for (int i = length / 2 - 1; i >= 0; i--) {
                maxHeapify(i);
            }
            verify();
        }

        private void verify(int i) {
            assert (i < length);
            var left = 2 * i + 1;
            var right = 2 * i + 2;
            if (left < length) {
                assert (arr[i] >= arr[left]);
                verify(left);
            }
            if (right < length) {
                assert (arr[i] >= arr[right]);
                verify(right);
            }
        }

        private void verify() {
            if (length != 0) {
                verify(0);
            }
        }

        // O(1)
        public boolean isEmpty() {
            return length == 0;
        }

        // O(logN)
        public int poll() {
            assert (!isEmpty());
            var ret = arr[0];
            if (length > 1) {
                swap(0, length - 1);
                length--;
                maxHeapify(0);
            } else {
                length--;
            }
            verify();
            return ret;
        }

        // O(logN)
        public void add(int e) {
            if (length == arr.length) {
                // expand underlying array
                arr = Arrays.copyOf(arr, arr.length + 100);
            }
            arr[length++] = e;
            // fix potential violation; go up level by level
            var i = length - 1;
            int parent;
            while (true) {
                parent = (i - 1) / 2;
                if (i == 0 || arr[parent] >= arr[i]) break;
                swap(parent, i);
                i = parent;
            }
            verify();
        }

        public static Heap fromArrayInplace(int[] arr) {
            return new Heap(arr);
        }

        public static Heap fromArray(int[] arr) {
            return new Heap(arr.clone());
        }

        // heap sort inplace
        public static void heapSort(int[] arr) {
            var heap = fromArrayInplace(arr);
            while (heap.length > 1) {
                // first element is the largest; place it in the end
                heap.swap(0, heap.length - 1);
                // logically shrinking the heap
                heap.length--;
                // fix potential violation
                heap.maxHeapify(0);
            }
        }
    }

    static class QCRunner {
        static final int TESTMAX = 100000;
        static Random rand = new Random();

        static int[] generate_ints() {
            return rand.ints(rand.nextInt(10) + 1).toArray();
        }

        static void qc_heap_sort() {
            for (int i = 0; i < TESTMAX; ++i) {
                var o_arr = generate_ints();
                var a_arr = o_arr.clone();
                Arrays.sort(a_arr);
                var b_arr = o_arr.clone();
                Heap.heapSort(b_arr);
                assert (Arrays.equals(a_arr, b_arr));
            }
        }

        static void qc_heap_poll() {
            for (int i = 0; i < TESTMAX; ++i) {
                var o_arr = generate_ints();
                var a_queue = new PriorityQueue<Integer>(o_arr.length, Collections.reverseOrder());
                a_queue.addAll(Arrays.stream(o_arr).boxed().collect(Collectors.toList()));
                var b_queue = Heap.fromArray(o_arr);
                while (!a_queue.isEmpty()) {
                    var a = a_queue.poll();
                    var b = b_queue.poll();
                    assert (a == b);
                }
                assert (b_queue.isEmpty());
            }
        }

        static void qc_heap_add() {
            for (int i = 0; i < TESTMAX; ++i) {
                var o_arr = generate_ints();
                var a_queue = new PriorityQueue<Integer>(o_arr.length, Collections.reverseOrder());
                var b_queue = Heap.fromArray(new int[0]);
                for (var e : o_arr) {
                    a_queue.add(e);
                    b_queue.add(e);
                }
                while (!a_queue.isEmpty()) {
                    var a = a_queue.poll();
                    var b = b_queue.poll();
                    assert (a == b);
                }
                assert (b_queue.isEmpty());
            }
        }

        static void check() throws Exception {
            // only run it when assertion is on
            var is_assert_on = false;
            assert is_assert_on = true;
            if (!is_assert_on) {
                throw new Exception("assertion no enabled");
            }
            qc_heap_sort();
            qc_heap_poll();
            qc_heap_add();
            System.out.println("Success");
        }
    }

    static int exec(Class<?> clazz, List<String> jvmArgs) throws IOException,
            InterruptedException {
        String javaHome = System.getProperty("java.home");
        String javaBin = javaHome + File.separator + "bin" + File.separator + "java";
        String classpath = System.getProperty("java.class.path");
        String className = clazz.getName();

        List<String> command = new ArrayList<>();
        command.add(javaBin);
        command.addAll(jvmArgs);
        command.add("-cp");
        command.add(classpath);
        command.add(className);

        ProcessBuilder builder = new ProcessBuilder(command);
        Process process = builder.inheritIO().start();
        process.waitFor();
        return process.exitValue();
    }

    static void config_jvm(String[] jvm_args) throws Exception {
        String custom_jvm_args = "custom_jvm_args";

        if (System.getProperty(custom_jvm_args) == null) {
            var flags = new ArrayList<>(Arrays.asList(jvm_args));
            flags.add(0, "-D" + custom_jvm_args);
            var ret = exec(Main.class, flags);
            System.exit(ret);
        }
    }

    public static void main(String[] args) throws Exception {
        config_jvm(new String[]{
          "-ea", // enable assertion
        });

        QCRunner.check();
    }
}

§references

• https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/tutorial/
• https://www.youtube.com/watch?v=B7hVxCmfPtM
• https://dzone.com/articles/running-a-java-class-as-a-subprocess