Subversion Repositories Code-Repo

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