- All Implemented Interfaces:
IntPriorityQueue
,Copyable<IntFibonacciHeap>
Origin: Fibonacci heaps were first introduced in the following article: M. L. Fredman and R. E. Tarjan (1987). Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Journal of the ACM, 34(3): 596-615, July 1987.
Priority order: IntFibonacciHeap instances are created via factory methods with names
beginning with create
. The priority order depends upon the factory method used to
create the IntFibonacciHeap. Methods named createMinHeap
produce a min heap with
priority order minimum-priority-first-out. Methods named createMaxHeap
produce a max
heap with priority order maximum-priority-first-out.
Creating instances: To create an instance, use one of the factory methods. In this example an IntFibonacciHeap with an element domain of [0,100) is created:
IntFibonacciHeap<String> pq = IntFibonacciHeap.createMinHeap(100);
In the above example, the element domain is [0,100) and the IntFibonacciHeap is initially empty.
Purpose: The purpose of such an IntFibonacciHeap is to support implementations of
algorithms that require such a specialized case. For example, some graph algorithms such as
Dijkstra's algorithm for single-source shortest paths, and Prim's algorithm for minimum spanning
tree, rely on a priority queue of the vertex ids, which are usually ints in some finite range.
Although such applications could use the classes that instead implement the PriorityQueue
interface, using Java's wrapper type Integer
, the classes that implement IntPriorityQueue
that specialize the element type to int are optimized for this special case.
For a more general purpose binary heap, see the FibonacciHeap
class.
Method runtimes: The asymptotic runtime of the methods of this class are as follows (where n is the current size of the heap). Note that in many cases in this list, the runtimes are amortized time and not actual time (see a reference on Fibonacci heaps for details).
- O(1):
contains(int)
,createMaxHeap(int)
,createMinHeap(int)
,domain()
,isEmpty()
,offer(int, int)
,peek()
,peekPriority()
,peekPriority(int)
,promote(int,int)
,size()
- O(lg n):
demote(int,int)
,poll()
- O(n):
clear()
,copy()
The amortized runtime of change(int,int)
depends on the direction of change. If the
priority is decreased for a min-heap or increased for a max-heap, the amortized runtime of change(int,int)
is O(1); but if the priority is increased for a min-heap or decreased for a
max-heap, then the amortized time of change(int,int)
is O(lg n).
-
Method Summary
Modifier and TypeMethodDescriptionboolean
change
(int element, int priority) Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.final void
clear()
Clears the IntPriorityQueue, removing all elements.final boolean
contains
(int element) Checks if an element is in the IntPriorityQueue.copy()
Creates an identical copy of this object.static IntFibonacciHeap
createMaxHeap
(int n) Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).static IntFibonacciHeap
createMinHeap
(int n) Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).boolean
demote
(int element, int priority) Demotes an element relative to priority order if the element is present in the IntPriorityQueue.final int
domain()
Returns the domain of this IntPriorityQueue.final boolean
isEmpty()
Checks if the IntPriorityQueue is empty.boolean
offer
(int element, int priority) Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.final int
peek()
Gets the next element in priority order from this IntPriorityQueue, without removing it.int
Gets the priority of the next element in priority order in the IntPriorityQueue.int
peekPriority
(int element) Gets the current priority of a specified element in the IntPriorityQueue.final int
poll()
Gets and removes the next element in priority order from this IntPriorityQueue.boolean
promote
(int element, int priority) Promotes an element relative to priority order if the element is present in the IntPriorityQueue.final int
size()
Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.
-
Method Details
-
copy
Description copied from interface:Copyable
Creates an identical copy of this object.- Specified by:
copy
in interfaceCopyable<IntFibonacciHeap>
- Returns:
- an identical copy of this object.
-
change
public boolean change(int element, int priority) Changes the priority of an element if the element is present in the IntPriorityQueue, and otherwise adds the (element, priority) pair to the IntPriorityQueue.- Specified by:
change
in interfaceIntPriorityQueue
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the IntPriorityQueue changed as a consequence of this method call.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n.
-
clear
public final void clear()Description copied from interface:IntPriorityQueue
Clears the IntPriorityQueue, removing all elements.- Specified by:
clear
in interfaceIntPriorityQueue
-
contains
public final boolean contains(int element) Checks if an element is in the IntPriorityQueue.- Specified by:
contains
in interfaceIntPriorityQueue
- Parameters:
element
- The element to check for containment.- Returns:
- true if and only if there exists an (element, priority) pair for the specified element.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n.
-
createMaxHeap
Initializes an empty max-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).- Parameters:
n
- The size of the domain of the elements of the max-heap.- Returns:
- an empty max-heap
- Throws:
IllegalArgumentException
- if n is non-positive
-
createMinHeap
Initializes an empty min-heap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).- Parameters:
n
- The size of the domain of the elements of the min-heap.- Returns:
- an empty min-heap
- Throws:
IllegalArgumentException
- if n is non-positive
-
demote
public boolean demote(int element, int priority) Demotes an element relative to priority order if the element is present in the IntPriorityQueue. For a min-heap, demotion means increasing the element's priority, while for a max-heap, demotion means decreasing its priority. If the element is not in the IntPriorityQueue, or if its new priority is not a demotion, then this method does nothing.- Specified by:
demote
in interfaceIntPriorityQueue
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the IntPriorityQueue changed as a consequence of this method call.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n.
-
domain
public final int domain()Description copied from interface:IntPriorityQueue
Returns the domain of this IntPriorityQueue. Note that the domain is not the same thing as the size. The domain defines the elements that are allowed in the IntPriorityQueue, whether or not they actually appear within it.- Specified by:
domain
in interfaceIntPriorityQueue
- Returns:
- the domain of this IntPriorityQueue
-
isEmpty
public final boolean isEmpty()Description copied from interface:IntPriorityQueue
Checks if the IntPriorityQueue is empty.- Specified by:
isEmpty
in interfaceIntPriorityQueue
- Returns:
- true if and only if it is empty
-
offer
public boolean offer(int element, int priority) Adds an (element, priority) pair to the IntPriorityQueue with a specified priority, provided the element is not already in the IntPriorityQueue.- Specified by:
offer
in interfaceIntPriorityQueue
- Parameters:
element
- The element.priority
- The priority of the element.- Returns:
- true if the (element, priority) pair was added, and false if the IntPriorityQueue already contained the element.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n.
-
peek
public final int peek()Gets the next element in priority order from this IntPriorityQueue, without removing it. Behavior is undefined if it is empty.- Specified by:
peek
in interfaceIntPriorityQueue
- Returns:
- the next element in priority order.
- Throws:
NullPointerException
- if empty
-
peekPriority
public int peekPriority()Gets the priority of the next element in priority order in the IntPriorityQueue. Behavior is undefined if it is empty.- Specified by:
peekPriority
in interfaceIntPriorityQueue
- Returns:
- the priority of the next element in priority order.
- Throws:
NullPointerException
- if empty
-
peekPriority
public int peekPriority(int element) Gets the current priority of a specified element in the IntPriorityQueue. Behavior is undefined if the IntPriorityQueue doesn't contain the element.- Specified by:
peekPriority
in interfaceIntPriorityQueue
- Parameters:
element
- the element whose priority is returned- Returns:
- the current priority of element.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n. * @throws NullPointerException if element is not in the heap
-
poll
public final int poll()Description copied from interface:IntPriorityQueue
Gets and removes the next element in priority order from this IntPriorityQueue. Behavior is undefined if it is empty.- Specified by:
poll
in interfaceIntPriorityQueue
- Returns:
- the next element in priority order.
-
promote
public boolean promote(int element, int priority) Promotes an element relative to priority order if the element is present in the IntPriorityQueue. For a min-heap, promotion means decreasing the element's priority, while for a max-heap, promotion means increasing its priority. If the element is not in the IntPriorityQueue, or if its new priority is not a promotion, then this method does nothing.- Specified by:
promote
in interfaceIntPriorityQueue
- Parameters:
element
- The element whose priority is to change.priority
- Its new priority.- Returns:
- true if and only if the IntPriorityQueue changed as a consequence of this method call.
- Throws:
IndexOutOfBoundsException
- if element is negative, or if element is greater than or equal to the domain n.
-
size
public final int size()Description copied from interface:IntPriorityQueue
Gets the current size of the IntPriorityQueue, which is the number of (element, priority) pairs that it contains.- Specified by:
size
in interfaceIntPriorityQueue
- Returns:
- the current size of the IntPriorityQueue.
-