MinHeap

MinHeap.java

package net.fehmicansaglam.minheap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

@SuppressWarnings("unused")
public class MinHeap<K, V extends Comparable<V>, T extends MinHeap.Item<K, V>> {

    public interface Item<K, V extends Comparable<V>> {
        K getKey();

        V getValue();

        void updateValue(V value);
    }

    private final List<T> items;
    private final Map<K, Integer> map;

    public MinHeap() {
        this(0);
    }

    public MinHeap(int size) {
        items = new ArrayList<>(size);
        map = new HashMap<>(size);
    }

    public MinHeap(ArrayList<T> items) {
        this.items = items;
        this.map = new HashMap<>(items.size());

        for (int i = 0; i < items.size(); i++) {
            this.map.put(items.get(i).getKey(), i);
        }

        buildHeap();
    }

    public void decreaseKey(K key, V value) {
        Integer i = this.map.get(key);
        if (i == null) {
            return;
        }

        T item = items.get(i);
        item.updateValue(value);
        int parent = parent(i);
        while (parent != i && items.get(i).getValue().compareTo(items.get(parent).getValue()) < 0) {
            swap(i, parent);
            i = parent;
            parent = parent(i);
        }
    }

    public void delete(K key) {
        Integer i = this.map.remove(key);
        if (i == null) {
            return;
        }

        int lastIndex = items.size() - 1;
        T last = items.remove(lastIndex);

        if (i < lastIndex) {
            items.set(i, last);
            this.map.put(last.getKey(), i);
            heapify(i);
        }
    }

    public void insert(T item) {
        int i = items.size();
        items.add(item);
        this.map.put(item.getKey(), i);
        int parent = parent(i);
        while (parent != i && items.get(i).getValue().compareTo(items.get(parent).getValue()) < 0) {
            swap(i, parent);
            i = parent;
            parent = parent(i);
        }
    }

    public T extractMin() {
        if (items.size() == 0)
            return null;

        this.map.remove(items.get(0).getKey());

        if (items.size() == 1)
            return items.remove(0);
        T min = items.get(0);
        T last = items.remove(items.size() - 1);
        items.set(0, last);
        this.map.put(last.getKey(), 0);
        heapify(0);
        return min;
    }

    public T min() {
        return items.get(0);
    }

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

    public int size() {
        return items.size();
    }

    public void print() {
        for (T item : items) System.out.print(item + ", ");
        System.out.println();
        System.out.println(this.map);
    }

    private void buildHeap() {
        for (int i = (items.size() / 2); i >= 0; i--)
            heapify(i);
    }

    private void heapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < items.size() && items.get(l).getValue().compareTo(items.get(i).getValue()) < 0)
            smallest = l;
        if (r < items.size() && items.get(r).getValue().compareTo(items.get(smallest).getValue()) < 0)
            smallest = r;
        if (smallest != i) {
            swap(i, smallest);
            heapify(smallest);
        }
    }

    private void swap(int i1, int i2) {
        this.map.put(items.get(i1).getKey(), i2);
        this.map.put(items.get(i2).getKey(), i1);

        T temp = items.get(i1);
        items.set(i1, items.get(i2));
        items.set(i2, temp);
    }

    private int parent(int i) {
        return i / 2;
    }

    private int left(int i) {
        return 2 * i;
    }

    private int right(int i) {
        return 2 * i + 1;
    }
}

MinHeapTest.java

package net.fehmicansaglam.minheap;

public class MinHeapTest {

    static final class Node implements MinHeap.Item<Integer, Integer> {
        private final int key; //key
        private int value; //priority

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public Integer getKey() {
            return this.key;
        }

        @Override
        public Integer getValue() {
            return this.value;
        }

        @Override
        public void updateValue(Integer value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{key=" + key + ", value=" + value + '}';
        }
    }


    public static void main(String[] args) {
        MinHeap<Integer, Integer, Node> heap = new MinHeap<>();
        heap.insert(new Node(0, 2));
        heap.insert(new Node(1, 1));
        heap.insert(new Node(2, 7));
        heap.insert(new Node(3, 5));
        heap.insert(new Node(5, 9));
        heap.insert(new Node(6, 11));
        heap.insert(new Node(7, 8));
        heap.insert(new Node(8, 6));

        heap.decreaseKey(2, 4);
        heap.delete(1);
        heap.delete(7);

        assert heap.extractMin().getValue() == 2;
        assert heap.extractMin().getValue() == 4;
        assert heap.extractMin().getValue() == 5;
        assert heap.extractMin().getValue() == 6;
        assert heap.extractMin().getValue() == 9;
        assert heap.extractMin().getValue() == 11;
    }
}