0,0 → 1,139 |
import java.nio.ByteBuffer; |
|
/** Max-heap implementation */ |
public class MaxHeap { |
private LRUBuffer Heap; // Pointer to the heap array |
private long size; // Number of things in heap |
|
private byte[] record1 = new byte[4]; |
private byte[] record2 = new byte[4]; |
private ByteBuffer buff1; |
private ByteBuffer buff2; |
|
/** Constructor supporting preloading of heap contents */ |
public MaxHeap(LRUBuffer buf, long size) { |
this.Heap = buf; |
this.size = size; |
} |
|
/** @return True if pos a leaf position, false otherwise */ |
public boolean isLeaf(long pos) { |
return (pos >= size / 2) && (pos < size); |
} |
|
/** @return Position for left child of pos */ |
public long leftchild(long pos) { |
assert pos < size / 2 : "Position has no left child"; |
return 2 * pos + 1; |
} |
|
/** @return Position for right child of pos */ |
public long rightchild(long pos) { |
assert pos < (size - 1) / 2 : "Position has no right child"; |
return 2 * pos + 2; |
} |
|
/** @return Position for parent */ |
public long parent(long pos) { |
assert pos > 0 : "Position has no parent"; |
return (pos - 1) / 2; |
} |
|
/** Heapify contents of Heap */ |
public void buildheap() { |
for (long i = size / 2 - 1; i >= 0; i--) |
siftdown(i); |
} |
|
/** Put element in its correct place */ |
private void siftdown(long pos) { |
assert (pos >= 0) && (pos < size) : "Illegal heap position"; |
|
while (!isLeaf(pos)) { |
long j = leftchild(pos); |
|
// if ((j < (size - 1)) && (Heap[j].compareTo(Heap[j + 1]) < 0)) |
// j++; // j is now index of child with greater value |
if (j < (size-1)) { |
Heap.getBytes(record1, j); |
buff1 = ByteBuffer.wrap(record1); |
short val1 = buff1.getShort(); |
Heap.getBytes(record2, j+1); |
buff2 = ByteBuffer.wrap(record2); |
short val2 = buff2.getShort(); |
if (val1 < val2) { |
j++; // j is now index of child with greater value |
} |
|
} |
|
// if (Heap[pos].compareTo(Heap[j]) >= 0) |
// return; |
Heap.getBytes(record2, j); |
Heap.getBytes(record1, pos); |
buff1 = ByteBuffer.wrap(record1); |
buff2 = ByteBuffer.wrap(record2); |
short val1 = buff1.getShort(); |
short val2 = buff2.getShort(); |
if (val1 >= val2) |
return; |
|
// DSutil.swap(Heap, pos, j); |
Heap.putBytes(record2, pos); |
Heap.putBytes(record1, j); |
|
pos = j; // Move down |
} |
} |
|
/** Remove and return maximum value */ |
public void removemax() { |
assert size > 0 : "Removing from empty heap"; |
|
//DSutil.swap(Heap, 0, --size); // Swap maximum with last value |
Heap.getBytes(record1, 0); |
Heap.getBytes(record2, size-1); |
Heap.putBytes(record1, size-1); |
Heap.putBytes(record2, 0); |
|
size = size - 1; |
if (size != 0) // Not on last element |
siftdown(0); // Put new heap root val in correct place |
} |
|
|
// /** @return Current size of the heap */ |
// public long heapsize() { |
// return size; |
// } |
|
// /** Insert val into heap */ |
// public void insert(E val) { |
// assert n < size : "Heap is full"; |
// int curr = n++; |
// Heap[curr] = val; // Start at end of heap |
// // Now sift up until curr's parent's key > curr's key |
// while ((curr != 0) && (Heap[curr].compareTo(Heap[parent(curr)]) > 0)) { |
// DSutil.swap(Heap, curr, parent(curr)); |
// curr = parent(curr); |
// } |
// } |
|
// /** Remove and return element at specified position */ |
// public E remove(int pos) { |
// assert (pos >= 0) && (pos < n) : "Illegal heap position"; |
// if (pos == (n - 1)) |
// n--; // Last element, no work to be done |
// else { |
// DSutil.swap(Heap, pos, --n); // Swap with last value |
// // If we just swapped in a big value, push it up |
// while ((pos > 0) && (Heap[pos].compareTo(Heap[parent(pos)]) > 0)) { |
// DSutil.swap(Heap, pos, parent(pos)); |
// pos = parent(pos); |
// } |
// if (n != 0) |
// siftdown(pos); // If it is little, push down |
// } |
// return Heap[n]; |
// } |
} |