Heap Implementation in JAVA

This is my Java implementation of the Heap data structure. The Heap data structure is also known as the PriorityQueue in the Java standard library. It is a binary tree that can be represented with the Arrays data structure or one of the List data types, preferably the ArrayList. I chose to use the ArrayList as the buffer of the Heap because of its dynamic resizing property, and the Heap's need for random access of the elements in the buffer. The Heap exhibit a nice property which allows for efficient polling of the min or max value from a set of numbers. This makes it a great optimization for algorithms such as Dijkstra where you need to extract the neighbor with the min cost. The methods this Heap supports are isEmpty, peek, add, and poll.

public static class Heap {
    public static final int MIN_HEAP = 0;
    public static final int MAX_HEAP = 1;

    private List<Integer> buffer;
    private int type;

    public Heap(int k) {
        type = k;
        buffer = new ArrayList<Integer>();
    }

    public Heap() {
        this(MIN_HEAP);
    }

    public boolean isEmpty() {
        return buffer.size() == 0;
    }

    public int peek() {
        return buffer.get(0);
    }

    public void add(int d) {
        buffer.add(d);
        percolateUp(buffer.size() - 1);
    }

    public Integer poll() {
        if (isEmpty()) return null;

        int d = buffer.get(0);
        buffer.set(0, buffer.get(buffer.size() - 1));
        buffer.remove(buffer.size() - 1);
        percolateDown(0);

        return d;
    }

    private void percolateUp(int i) {
        if (isEmpty()) return;

        while (i > 0) {
            int parent = i >> 1;
            if (i % 2 == 0) parent -= 1;

            if ((type == MIN_HEAP && buffer.get(parent) < buffer.get(i)) ||
            (type == MAX_HEAP && buffer.get(parent) > buffer.get(i)))
                break;

            int temp = buffer.get(i);
            buffer.set(i, buffer.get(parent));
            buffer.set(parent, temp);

            i = parent;
        }
    }

    private void percolateDown(int i) {
        if (isEmpty()) return;

        while (i < buffer.size() >> 1) {
            int child = (i << 1) + 1;

            if ((type == MIN_HEAP && child + 1 < buffer.size() && buffer.get(child + 1) < buffer.get(child)) ||
            (type == MAX_HEAP && child + 1 < buffer.size() && buffer.get(child + 1) > buffer.get(child)))
                child++;

            if ((type == MIN_HEAP && buffer.get(child) > buffer.get(i)) ||
            (type == MAX_HEAP && buffer.get(child) < buffer.get(i)))
                break;

            int temp = buffer.get(i);
            buffer.set(i, buffer.get(child));
            buffer.set(child, temp);
        }
    }
}

This article is my 12th oldest. It is 335 words long, and it’s got 0 comments for now.