utils/dataStructures/BinaryHeap.java

package ags.utils.dataStructures;

import java.util.Arrays;

/**
 * An implementation of an implicit binary heap. Min-heap and max-heap both supported 
 */
public abstract class BinaryHeap<T> {
    protected static final int defaultCapacity = 64;
    private final int direction;
    private Object[] data;
    private double[] keys;
    private int capacity;
    private int size;

    protected BinaryHeap(int capacity, int direction) {
        this.direction = direction;
        this.data = new Object[capacity];
        this.keys = new double[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    public void offer(double key, T value) {
        // If move room is needed, double array size
        if (size >= capacity) {
            capacity *= 2;
            data = Arrays.copyOf(data, capacity);
            keys = Arrays.copyOf(keys, capacity);
        }

        // Insert new value at the end
        data[size] = value;
        keys[size] = key;
        siftUp(size);
        size++;
    }

    protected void removeTip() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        size--;
        data[0] = data[size];
        keys[0] = keys[size];
        data[size] = null;
        siftDown(0);
    }
    
    protected void replaceTip(double key, T value) {
        if (size == 0) {
            throw new IllegalStateException();
        }

        data[0] = value;
        keys[0] = key;
        siftDown(0);
    }

    @SuppressWarnings("unchecked")
    protected T getTip() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        return (T) data[0];
    }

    protected double getTipKey() {
        if (size == 0) {
            throw new IllegalStateException();
        }

        return keys[0];
    }

    private void siftUp(int c) {
        for (int p = (c - 1) / 2; c != 0 && direction*keys[c] > direction*keys[p]; c = p, p = (c - 1) / 2) {
            Object pData = data[p];
            double pDist = keys[p];
            data[p] = data[c];
            keys[p] = keys[c];
            data[c] = pData;
            keys[c] = pDist;
        }
    }

    private void siftDown(int p) {
        for (int c = p * 2 + 1; c < size; p = c, c = p * 2 + 1) {
            if (c + 1 < size && direction*keys[c] < direction*keys[c + 1]) {
                c++;
            }
            if (direction*keys[p] < direction*keys[c]) {
                // Swap the points
                Object pData = data[p];
                double pDist = keys[p];
                data[p] = data[c];
                keys[p] = keys[c];
                data[c] = pData;
                keys[c] = pDist;
            } else {
                break;
            }
        }
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return capacity;
    }

    public static final class Max<T> extends BinaryHeap<T> implements MaxHeap<T> {
        public Max() {
            super(defaultCapacity, 1);
        }
        public Max(int capacity) {
            super(capacity, 1);
        }
        public void removeMax() {
            removeTip();
        }
        public void replaceMax(double key, T value) {
            replaceTip(key, value);
        }
        public T getMax() {
            return getTip();
        }
        public double getMaxKey() {
            return getTipKey();
        }
    }
    public static final class Min<T> extends BinaryHeap<T> implements MinHeap<T> {
        public Min() {
            super(defaultCapacity, -1);
        }
        public Min(int capacity) {
            super(capacity, -1);
        }
        public void removeMin() {
            removeTip();
        }
        public void replaceMin(double key, T value) {
            replaceTip(key, value);
        }
        public T getMin() {
            return getTip();
        }
        public double getMinKey() {
            return getTipKey();
        }
    }
}
1	package ags.utils.dataStructures;
2
3	import java.util.Arrays;
4
5	/**
6	* An implementation of an implicit binary heap. Min-heap and max-heap both supported
7	*/
8	public abstract class BinaryHeap<T> {
9	protected static final int defaultCapacity = 64;
10	private final int direction;
11	private Object[] data;
12	private double[] keys;
13	private int capacity;
14	private int size;
15
16	protected BinaryHeap(int capacity, int direction) {
17	this.direction = direction;
18	this.data = new Object[capacity];
19	this.keys = new double[capacity];
20	this.capacity = capacity;
21	this.size = 0;
22	}
23
24	public void offer(double key, T value) {
25	// If move room is needed, double array size
26	if (size >= capacity) {
27	capacity *= 2;
28	data = Arrays.copyOf(data, capacity);
29	keys = Arrays.copyOf(keys, capacity);
30	}
31
32	// Insert new value at the end
33	data[size] = value;
34	keys[size] = key;
35	siftUp(size);
36	size++;
37	}
38
39	protected void removeTip() {
40	if (size == 0) {
41	throw new IllegalStateException();
42	}
43
44	size--;
45	data[0] = data[size];
46	keys[0] = keys[size];
47	data[size] = null;
48	siftDown(0);
49	}
50
51	protected void replaceTip(double key, T value) {
52	if (size == 0) {
53	throw new IllegalStateException();
54	}
55
56	data[0] = value;
57	keys[0] = key;
58	siftDown(0);
59	}
60
61	@SuppressWarnings("unchecked")
62	protected T getTip() {
63	if (size == 0) {
64	throw new IllegalStateException();
65	}
66
67	return (T) data[0];
68	}
69
70	protected double getTipKey() {
71	if (size == 0) {
72	throw new IllegalStateException();
73	}
74
75	return keys[0];
76	}
77
78	private void siftUp(int c) {
79	for (int p = (c - 1) / 2; c != 0 && directionkeys[c] > directionkeys[p]; c = p, p = (c - 1) / 2) {
80	Object pData = data[p];
81	double pDist = keys[p];
82	data[p] = data[c];
83	keys[p] = keys[c];
84	data[c] = pData;
85	keys[c] = pDist;
86	}
87	}
88
89	private void siftDown(int p) {
90	for (int c = p * 2 + 1; c < size; p = c, c = p * 2 + 1) {
91	if (c + 1 < size && directionkeys[c] < directionkeys[c + 1]) {
92	c++;
93	}
94	if (directionkeys[p] < directionkeys[c]) {
95	// Swap the points
96	Object pData = data[p];
97	double pDist = keys[p];
98	data[p] = data[c];
99	keys[p] = keys[c];
100	data[c] = pData;
101	keys[c] = pDist;
102	} else {
103	break;
104	}
105	}
106	}
107
108	public int size() {
109	return size;
110	}
111
112	public int capacity() {
113	return capacity;
114	}
115
116	public static final class Max<T> extends BinaryHeap<T> implements MaxHeap<T> {
117	public Max() {
118	super(defaultCapacity, 1);
119	}
120	public Max(int capacity) {
121	super(capacity, 1);
122	}
123	public void removeMax() {
124	removeTip();
125	}
126	public void replaceMax(double key, T value) {
127	replaceTip(key, value);
128	}
129	public T getMax() {
130	return getTip();
131	}
132	public double getMaxKey() {
133	return getTipKey();
134	}
135	}
136	public static final class Min<T> extends BinaryHeap<T> implements MinHeap<T> {
137	public Min() {
138	super(defaultCapacity, -1);
139	}
140	public Min(int capacity) {
141	super(capacity, -1);
142	}
143	public void removeMin() {
144	removeTip();
145	}
146	public void replaceMin(double key, T value) {
147	replaceTip(key, value);
148	}
149	public T getMin() {
150	return getTip();
151	}
152	public double getMinKey() {
153	return getTipKey();
154	}
155	}
156	}