5 public class Heap<V, K> {
6 private static final Object[] empty = {};
7 private final Comparator<? super K> cmp;
8 private final Map<V, Integer> index = new IdentityHashMap<>();
9 private Object[] vbuf = empty, kbuf = empty;
12 public Heap(Comparator<? super K> cmp) {
16 @SuppressWarnings("unchecked")
17 private V val(int i) {return((V)vbuf[i]);}
18 @SuppressWarnings("unchecked")
19 private K key(int i) {return((K)kbuf[i]);}
21 private void raise(V val, K key, int i) {
23 int p = (i - 1) >>> 1;
24 if(cmp.compare(key(p), key) <= 0)
36 private void lower(V val, K key, int i) {
38 int c1 = (i << 1) + 1, c2 = c1 + 1;
41 int c = ((c2 < size) && (cmp.compare(key(c1), key(c2)) > 0)) ? c2 : c1;
42 if(cmp.compare(key(c), key) > 0)
54 private void adjust(V val, K key, int i) {
55 if((i > 0) && cmp.compare(key((i - 1) >> 1), key) > 0)
66 return((size > 0) ? val(0) : null);
79 throw(new NoSuchElementException());
86 return((size > 0) ? key(0) : null);
89 public void add(V val, K key) {
90 if(index.containsKey(val))
91 throw(new IllegalStateException());
93 if(p >= vbuf.length) {
94 int n = Math.max(vbuf.length * 2, 16);
95 vbuf = Arrays.copyOf(vbuf, n);
96 kbuf = Arrays.copyOf(kbuf, n);
101 public K update(V val, K key) {
102 Integer p = index.get(val);
104 throw(new NoSuchElementException());
110 public K set(V val, K key) {
111 Integer p = index.get(val);
121 private K remove(int p) {
125 } else if(p < size) {
126 adjust(val(size), key(size), p);
128 throw(new AssertionError());
135 public K remove(V val) {
136 Integer p = index.remove(val);
142 public boolean contains(V val) {
143 return(index.containsKey(val));
146 public String toString() {
147 StringBuilder buf = new StringBuilder();
149 for(int i = 0; i < size; i++) {
152 buf.append(String.valueOf(kbuf[i]));
154 buf.append(String.valueOf(vbuf[i]));
157 return(buf.toString());