Modifiable binary heap

UpdateHeap.java

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;

public class UpdateHeap<V> implements Iterable<V> {
    private final Comparator<V> comparator;
    private final HashMap<V, Entry> map;
    private Entry[] heap;
    private int size;

    public UpdateHeap() {
        this(null);
    }

    public UpdateHeap(Comparator<V> comparator) {
        this.comparator = comparator;
        this.map = new HashMap<>();
        this.heap = createArray();
        this.size = 0;
    }

    private Entry[] createArray() {
        Entry[] initial = Entry[].class.cast(Array.newInstance(Entry.class, 16));
        for (int i = 0; i < initial.length; i++)
            initial[i] = new Entry(i);
        return initial;
    }

    public void addOrUpdate(V value) {
        if (value == null)
            throw new IllegalArgumentException("UpdateHeap does not support null values");

        Entry entry = map.get(value);
        if (entry != null) {
            notifyChange(entry.index);
        } else {
            ensureHeap(size);
            entry = acquireItem(value);
            bubbleUp(entry.index);
            map.put(value, entry);
        }
    }

    public V remove(V value) {
        Entry entry = map.remove(value);
        if (entry != null)
            return removeAt(entry.index);

        return null;
    }

    private Entry acquireItem(V obj) {
        Entry entry = heap[size];
        entry.obj = obj;
        size++;
        return entry;
    }

    private void ensureHeap(int newSize) {
        while (heap.length <= newSize) {
            int oldSize = heap.length;
            heap = Arrays.copyOf(heap, heap.length * 2);
            for (int i = oldSize; i < heap.length; i++)
                heap[i] = new Entry(i);
        }
    }

    public V top() {
        return heap[0].obj;
    }

    public Iterator<V> iterator() {
        return new Iterator<V>() {
            private final Iterator<V> it = map.keySet().iterator();
            private V last;

            @Override
            public boolean hasNext() {
                return it.hasNext();
            }

            @Override
            public V next() {
                return last = it.next();
            }

            @Override
            public void remove() {
                if (last == null)
                    throw new IllegalStateException("Must call next() before removing");
                Entry entry = map.get(last);
                it.remove();
                removeAt(entry.index);
            }
        };
    }

    private V removeAt(int idx) {
        swap(idx, --size);
        bubbleDown(idx);
        V obj = heap[size].obj;
        heap[size].obj = null;
        return obj;
    }

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

    public int size() {
        return size;
    }

    private int notifyChange(int n) {
        return bubbleDown(bubbleUp(n));
    }

    private int bubbleUp(int n) {
        while (less(n, (n - 1) / 2))
            n = swap(n, (n - 1) / 2);

        return n;
    }

    private int bubbleDown(int n) {
        for (int k; (k = min(n, n * 2 + 1, n * 2 + 2)) != n && k < size; )
            n = swap(n, k);

        return n;
    }

    private int min(int i, int j, int k) {
        return min(i, min(j, k));
    }

    private int min(int i, int j) {
        return less(i, j) ? i : j;
    }

    private boolean less(int i, int j) {
        return i < size && (j >= size || compare(i, j) < 0);
    }

    private int compare(int i, int j) {
        if (comparator != null)
            return comparator.compare(heap[i].obj, heap[j].obj);
        else
            return ((Comparable) heap[i].obj).compareTo(heap[j].obj);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int i = 0; i < size; i++) {
            if (i > 0) builder.append(", ");
            builder.append(heap[i].obj);
        }
        return builder.append("]").toString();
    }

    private int swap(int i, int j) {
        heap[i].index = j;
        heap[j].index = i;
        Entry tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
        return j;
    }

    private class Entry {
        private V obj;
        private int index;

        public Entry(int index) {
            this.index = index;
        }
    }
}