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

//	}

}