Package org.apache.lucene.util
Class LongHeap
 java.lang.Object

 org.apache.lucene.util.LongHeap

public final class LongHeap extends Object
A min heap that stores longs; a primitive priority queue that like all priority queues maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size). This heap provides unbounded growth viapush(long)
, and boundedsize insertion based on its nominal maxSize viainsertWithOverflow(long)
. The heap is a min heap, meaning that the top element is the lowest value of the heap. NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.


Constructor Summary
Constructors Constructor Description LongHeap(int maxSize)
Create an empty priority queue of the configured initial size.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
Removes all entries from the PriorityQueue.long
get(int i)
Return the element at the ith location in the heap array.boolean
insertWithOverflow(long value)
Adds a value to an LongHeap in log(size) time.long
pop()
Removes and returns the least element of the PriorityQueue in log(size) time.long
push(long element)
Adds a value in log(size) time.void
pushAll(LongHeap other)
int
size()
Returns the number of elements currently stored in the PriorityQueue.long
top()
Returns the least element of the LongHeap in constant time.long
updateTop(long value)
Replace the top of the pq withnewTop
.



Method Detail

push
public final long push(long element)
Adds a value in log(size) time. Grows unbounded as needed to accommodate new values. Returns:
 the new 'top' element in the queue.

insertWithOverflow
public boolean insertWithOverflow(long value)
Adds a value to an LongHeap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded. Returns:
 whether the value was added (unless the heap is full, or the new value is less than the top value)

top
public final long top()
Returns the least element of the LongHeap in constant time. It is up to the caller to verify that the heap is not empty; no checking is done, and if no elements have been added, 0 is returned.

pop
public final long pop()
Removes and returns the least element of the PriorityQueue in log(size) time. Throws:
IllegalStateException
 if the LongHeap is empty.

updateTop
public final long updateTop(long value)
Replace the top of the pq withnewTop
. Should be called when the top value changes. Still log(n) worst case, but it's at least twice as fast topq.updateTop(value);
instead ofpq.pop(); pq.push(value);
Calling this method on an empty LongHeap has no visible effect. Parameters:
value
 the new element that is less than the current top. Returns:
 the new 'top' element after shuffling the heap.

size
public final int size()
Returns the number of elements currently stored in the PriorityQueue.

clear
public final void clear()
Removes all entries from the PriorityQueue.

pushAll
public void pushAll(LongHeap other)

get
public long get(int i)
Return the element at the ith location in the heap array. Use for iterating over elements when the order doesn't matter. Note that the valid arguments range from [1, size].

