| 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]; |
| // } |
| } |