Class PriorityQueue<T>

A PriorityQueue<T> maintains a partial ordering of its elements such that the element with least priority can always be found in constant time. Put()'s and Pop()'s require log(size) time.

NOTE: this class will pre-allocate a full array of length maxSize+1 if instantiated with a constructor that accepts a ISentinelFactory<T>. That maximum size can grow as we insert elements over time.

NOTE: The type of T may be either a class or a value type. But do note that it was specifically designed with nullable types in mind, so there may be cases where you need to use a nullable value type to get it to behave correctly.

Note

This API is for internal purposes only and might change in incompatible ways in the next release.

Inheritance
object
PriorityQueue<T>
FieldValueHitQueue<T>
Inherited Members
Namespace: Lucene.Net.Util
Assembly: Lucene.Net.dll
Syntax
public abstract class PriorityQueue<T>
Type Parameters
Name Description
T

Constructors

PriorityQueue(int)

Initializes a new instance of PriorityQueue<T> with the specified maxSize.

Declaration
protected PriorityQueue(int maxSize)
Parameters
Type Name Description
int maxSize

The maximum number of elements this queue can hold.

PriorityQueue(int, ISentinelFactory<T>?)

Initializes a new instance of PriorityQueue<T> with the specified maxSize and sentinelFactory.

Declaration
protected PriorityQueue(int maxSize, ISentinelFactory<T>? sentinelFactory)
Parameters
Type Name Description
int maxSize

The maximum number of elements this queue can hold.
ISentinelFactory<T> sentinelFactory

If not null, the queue will be pre-populated. This factory will be called maxSize times to get an instance to provide to each element in the queue. sentinelFactory should return a new instance on each call, but each sentinel instance should consistently represent the same value.
See Also

Properties

Count

Returns the number of elements currently stored in the PriorityQueue<T>. NOTE: This was size() in Lucene.

Declaration
public int Count { get; }
Property Value
Type Description
int

HeapArray

Gets the internal heap array as T[].

Note

This API is for internal purposes only and might change in incompatible ways in the next release.

Declaration
protected T[] HeapArray { get; }
Property Value
Type Description
T[]

Top

Returns the least element of the PriorityQueue<T> in constant time. Returns null if the queue is empty.

Declaration
public T Top { get; }
Property Value
Type Description
T

Methods

Add(T)

Adds an Object to a PriorityQueue<T> in log(size) time. If one tries to add more objects than maxSize from initialize and it is not possible to resize the heap, an IndexOutOfRangeException is thrown.

Declaration
public T Add(T element)
Parameters
Type Name Description
T element
Returns
Type Description
T

The new 'top' element in the queue.

Clear()

Removes all entries from the PriorityQueue<T>.

Declaration
public void Clear()

Insert(T)

Adds an Object to a PriorityQueue<T> in log(size) time. If the given element is smaller than then full heap's minimum, it won't be added.

Declaration
public virtual void Insert(T element)
Parameters
Type Name Description
T element

InsertWithOverflow(T)

Adds an Object to a PriorityQueue<T> in log(size) time. It returns the object (if any) that was dropped off the heap because it was full. This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements.

Declaration
public virtual T InsertWithOverflow(T element)
Parameters
Type Name Description
T element
Returns
Type Description
T

LessThan(T, T)

Determines the ordering of objects in this priority queue. Subclasses must define this one method.

Declaration
protected abstract bool LessThan(T a, T b)
Parameters
Type Name Description
T a
T b
Returns
Type Description
bool

true if parameter a is less than parameter b; othewise, false.

Pop()

Removes and returns the least element of the PriorityQueue<T> in log(size) time.

Declaration
public T Pop()
Returns
Type Description
T

UpdateTop()

Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to

pq.Top.Change();
pq.UpdateTop();

instead of

o = pq.Pop();
o.Change();
pq.Push(o);
Declaration
public T UpdateTop()
Returns
Type Description
T

The new 'top' element.