Class LongHeapIndirectPriorityQueue
- All Implemented Interfaces:
it.unimi.dsi.fastutil.IndirectPriorityQueue<Long>,LongIndirectPriorityQueue
Instances of this class use an additional inversion array, of the same length of the reference array,
to keep track of the heap position containing a given element of the reference array. The priority queue is
represented using a heap. The heap is enlarged as needed, but it is never
shrunk. Use the LongHeapSemiIndirectPriorityQueue.trim() method to reduce its size, if necessary.
-
Field Summary
FieldsFields inherited from class it.unimi.dsi.fastutil.longs.LongHeapSemiIndirectPriorityQueue
c, heap, refArray, size -
Constructor Summary
ConstructorsConstructorDescriptionLongHeapIndirectPriorityQueue(long[] refArray) Creates a new empty queue with capacity equal to the length of the reference array and using the natural order.LongHeapIndirectPriorityQueue(long[] refArray, int capacity) Creates a new empty queue with a given capacity and using the natural order.LongHeapIndirectPriorityQueue(long[] refArray, int[] a) Wraps a given array in a queue using the natural order.LongHeapIndirectPriorityQueue(long[] refArray, int[] a, int size) Wraps a given array in a queue using the natural order.LongHeapIndirectPriorityQueue(long[] refArray, int[] a, int size, it.unimi.dsi.fastutil.longs.LongComparator c) Wraps a given array in a queue using a given comparator.LongHeapIndirectPriorityQueue(long[] refArray, int[] a, it.unimi.dsi.fastutil.longs.LongComparator c) Wraps a given array in a queue using a given comparator.LongHeapIndirectPriorityQueue(long[] refArray, int capacity, it.unimi.dsi.fastutil.longs.LongComparator c) Creates a new empty queue with a given capacity and comparator.LongHeapIndirectPriorityQueue(long[] refArray, it.unimi.dsi.fastutil.longs.LongComparator c) Creates a new empty queue with capacity equal to the length of the reference array and a given comparator. -
Method Summary
Methods inherited from class it.unimi.dsi.fastutil.longs.LongHeapSemiIndirectPriorityQueue
comparator, ensureElement, first, front, size, toString, trimMethods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, waitMethods inherited from interface it.unimi.dsi.fastutil.IndirectPriorityQueue
isEmpty, last
-
Field Details
-
inv
protected final int[] invThe inversion array.
-
-
Constructor Details
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int capacity, it.unimi.dsi.fastutil.longs.LongComparator c) Creates a new empty queue with a given capacity and comparator.- Parameters:
refArray- the reference array.capacity- the initial capacity of this queue.c- the comparator used in this queue, ornullfor the natural order.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int capacity) Creates a new empty queue with a given capacity and using the natural order.- Parameters:
refArray- the reference array.capacity- the initial capacity of this queue.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, it.unimi.dsi.fastutil.longs.LongComparator c) Creates a new empty queue with capacity equal to the length of the reference array and a given comparator.- Parameters:
refArray- the reference array.c- the comparator used in this queue, ornullfor the natural order.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray) Creates a new empty queue with capacity equal to the length of the reference array and using the natural order.- Parameters:
refArray- the reference array.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int[] a, int size, it.unimi.dsi.fastutil.longs.LongComparator c) Wraps a given array in a queue using a given comparator.The queue returned by this method will be backed by the given array. The first
sizeelement of the array will be rearranged so to form a heap (this is more efficient than enqueing the elements ofaone by one).- Parameters:
refArray- the reference array.a- an array of indices intorefArray.size- the number of elements to be included in the queue.c- the comparator used in this queue, ornullfor the natural order.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int[] a, it.unimi.dsi.fastutil.longs.LongComparator c) Wraps a given array in a queue using a given comparator.The queue returned by this method will be backed by the given array. The elements of the array will be rearranged so to form a heap (this is more efficient than enqueing the elements of
aone by one).- Parameters:
refArray- the reference array.a- an array of indices intorefArray.c- the comparator used in this queue, ornullfor the natural order.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int[] a, int size) Wraps a given array in a queue using the natural order.The queue returned by this method will be backed by the given array. The first
sizeelement of the array will be rearranged so to form a heap (this is more efficient than enqueing the elements ofaone by one).- Parameters:
refArray- the reference array.a- an array of indices intorefArray.size- the number of elements to be included in the queue.
-
LongHeapIndirectPriorityQueue
public LongHeapIndirectPriorityQueue(long[] refArray, int[] a) Wraps a given array in a queue using the natural order.The queue returned by this method will be backed by the given array. The elements of the array will be rearranged so to form a heap (this is more efficient than enqueing the elements of
aone by one).- Parameters:
refArray- the reference array.a- an array of indices intorefArray.
-
-
Method Details
-
enqueue
public void enqueue(int x) - Specified by:
enqueuein interfaceit.unimi.dsi.fastutil.IndirectPriorityQueue<Long>- Overrides:
enqueuein classLongHeapSemiIndirectPriorityQueue
-
contains
public boolean contains(int index) -
dequeue
public int dequeue()- Specified by:
dequeuein interfaceit.unimi.dsi.fastutil.IndirectPriorityQueue<Long>- Overrides:
dequeuein classLongHeapSemiIndirectPriorityQueue
-
changed
public void changed()Description copied from class:LongHeapSemiIndirectPriorityQueueThe caller must guarantee that when this method is called the index of the first element appears just once in the queue. Failure to do so will bring the queue in an inconsistent state, and will cause unpredictable behaviour.
- Specified by:
changedin interfaceit.unimi.dsi.fastutil.IndirectPriorityQueue<Long>- Overrides:
changedin classLongHeapSemiIndirectPriorityQueue
-
changed
public void changed(int index) -
allChanged
public void allChanged()Rebuilds this queue in a bottom-up fashion (in linear time).- Specified by:
allChangedin interfaceit.unimi.dsi.fastutil.IndirectPriorityQueue<Long>- Overrides:
allChangedin classLongHeapSemiIndirectPriorityQueue
-
remove
public boolean remove(int index) -
clear
public void clear()- Specified by:
clearin interfaceit.unimi.dsi.fastutil.IndirectPriorityQueue<Long>- Overrides:
clearin classLongHeapSemiIndirectPriorityQueue
-