 All Implemented Interfaces:
IntPriorityQueueDouble
,Copyable<IntFibonacciHeapDouble>
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): 596615, July 1987.
Priority order: IntFibonacciHeapDouble instances are created via factory methods with
names beginning with create
. The priority order depends upon the factory method used
to create the IntFibonacciHeapDouble. Methods named createMinHeap
produce a min heap
with priority order minimumpriorityfirstout. Methods named createMaxHeap
produce
a max heap with priority order maximumpriorityfirstout.
Creating instances: To create an instance, use one of the factory methods. In this example an IntFibonacciHeapDouble with an element domain of [0,100) is created:
IntFibonacciHeapDouble<String> pq = IntFibonacciHeapDouble.createMinHeap(100);
In the above example, the element domain is [0,100) and the IntFibonacciHeapDouble is initially empty.
Purpose: The purpose of such an IntFibonacciHeapDouble is to support implementations of
algorithms that require such a specialized case. For example, some graph algorithms such as
Dijkstra's algorithm for singlesource 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 PriorityQueueDouble
interface, using Java's wrapper type Integer
, the classes that
implement IntPriorityQueueDouble
that specialize the element type to int are optimized
for this special case.
For a more general purpose binary heap, see the FibonacciHeapDouble
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, double)
,peek()
,peekPriority()
,peekPriority(int)
,promote(int,double)
,size()
 O(lg n):
demote(int,double)
,poll()
 O(n):
clear()
,copy()
The amortized runtime of change(int,double)
depends on the direction of change. If
the priority is decreased for a minheap or increased for a maxheap, the amortized runtime of
change(int,double)
is O(1); but if the priority is increased for a minheap or decreased
for a maxheap, then the amortized time of change(int,double)
is O(lg n).

Method Summary
Modifier and TypeMethodDescriptionboolean
change
(int element, double priority) Changes the priority of an element if the element is present in the IntPriorityQueueDouble, and otherwise adds the (element, priority) pair to the IntPriorityQueueDouble.final void
clear()
Clears the IntPriorityQueueDouble, removing all elements.final boolean
contains
(int element) Checks if an element is in the IntPriorityQueueDouble.copy()
Creates an identical copy of this object.static IntFibonacciHeapDouble
createMaxHeap
(int n) Initializes an empty maxheap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).static IntFibonacciHeapDouble
createMinHeap
(int n) Initializes an empty minheap of (int, priority) pairs, such that the domain of the elements are the integers in [0, n).boolean
demote
(int element, double priority) Demotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.final int
domain()
Returns the domain of this IntPriorityQueueDouble.final boolean
isEmpty()
Checks if the IntPriorityQueueDouble is empty.boolean
offer
(int element, double priority) Adds an (element, priority) pair to the IntPriorityQueueDouble with a specified priority, provided the element is not already in the IntPriorityQueueDouble.final int
peek()
Gets the next element in priority order from this IntPriorityQueueDouble, without removing it.double
Gets the priority of the next element in priority order in the IntPriorityQueueDouble.double
peekPriority
(int element) Gets the current priority of a specified element in the IntPriorityQueueDouble.final int
poll()
Gets and removes the next element in priority order from this IntPriorityQueueDouble.boolean
promote
(int element, double priority) Promotes an element relative to priority order if the element is present in the IntPriorityQueueDouble.final int
size()
Gets the current size of the IntPriorityQueueDouble, 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<IntFibonacciHeapDouble>
 Returns:
 an identical copy of this object.

change
public boolean change(int element, double priority) Changes the priority of an element if the element is present in the IntPriorityQueueDouble, and otherwise adds the (element, priority) pair to the IntPriorityQueueDouble. Specified by:
change
in interfaceIntPriorityQueueDouble
 Parameters:
element
 The element whose priority is to change.priority
 Its new priority. Returns:
 true if and only if the IntPriorityQueueDouble 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:IntPriorityQueueDouble
Clears the IntPriorityQueueDouble, removing all elements. Specified by:
clear
in interfaceIntPriorityQueueDouble

contains
public final boolean contains(int element) Checks if an element is in the IntPriorityQueueDouble. Specified by:
contains
in interfaceIntPriorityQueueDouble
 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 maxheap 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 maxheap. Returns:
 an empty maxheap
 Throws:
IllegalArgumentException
 if n is nonpositive

createMinHeap
Initializes an empty minheap 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 minheap. Returns:
 an empty minheap
 Throws:
IllegalArgumentException
 if n is nonpositive

demote
public boolean demote(int element, double priority) Demotes an element relative to priority order if the element is present in the IntPriorityQueueDouble. For a minheap, demotion means increasing the element's priority, while for a maxheap, demotion means decreasing its priority. If the element is not in the IntPriorityQueueDouble, or if its new priority is not a demotion, then this method does nothing. Specified by:
demote
in interfaceIntPriorityQueueDouble
 Parameters:
element
 The element whose priority is to change.priority
 Its new priority. Returns:
 true if and only if the IntPriorityQueueDouble 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:IntPriorityQueueDouble
Returns the domain of this IntPriorityQueueDouble. Note that the domain is not the same thing as the size. The domain defines the elements that are allowed in the IntPriorityQueueDouble, whether or not they actually appear within it. Specified by:
domain
in interfaceIntPriorityQueueDouble
 Returns:
 the domain of this IntPriorityQueueDouble

isEmpty
public final boolean isEmpty()Description copied from interface:IntPriorityQueueDouble
Checks if the IntPriorityQueueDouble is empty. Specified by:
isEmpty
in interfaceIntPriorityQueueDouble
 Returns:
 true if and only if it is empty

offer
public boolean offer(int element, double priority) Adds an (element, priority) pair to the IntPriorityQueueDouble with a specified priority, provided the element is not already in the IntPriorityQueueDouble. Specified by:
offer
in interfaceIntPriorityQueueDouble
 Parameters:
element
 The element.priority
 The priority of the element. Returns:
 true if the (element, priority) pair was added, and false if the IntPriorityQueueDouble 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 IntPriorityQueueDouble, without removing it. Behavior is undefined if it is empty. Specified by:
peek
in interfaceIntPriorityQueueDouble
 Returns:
 the next element in priority order.
 Throws:
NullPointerException
 if empty

peekPriority
public double peekPriority()Gets the priority of the next element in priority order in the IntPriorityQueueDouble. Behavior is undefined if it is empty. Specified by:
peekPriority
in interfaceIntPriorityQueueDouble
 Returns:
 the priority of the next element in priority order.
 Throws:
NullPointerException
 if empty

peekPriority
public double peekPriority(int element) Gets the current priority of a specified element in the IntPriorityQueueDouble. Behavior is undefined if the IntPriorityQueueDouble doesn't contain the element. Specified by:
peekPriority
in interfaceIntPriorityQueueDouble
 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:IntPriorityQueueDouble
Gets and removes the next element in priority order from this IntPriorityQueueDouble. Behavior is undefined if it is empty. Specified by:
poll
in interfaceIntPriorityQueueDouble
 Returns:
 the next element in priority order.

promote
public boolean promote(int element, double priority) Promotes an element relative to priority order if the element is present in the IntPriorityQueueDouble. For a minheap, promotion means decreasing the element's priority, while for a maxheap, promotion means increasing its priority. If the element is not in the IntPriorityQueueDouble, or if its new priority is not a promotion, then this method does nothing. Specified by:
promote
in interfaceIntPriorityQueueDouble
 Parameters:
element
 The element whose priority is to change.priority
 Its new priority. Returns:
 true if and only if the IntPriorityQueueDouble 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:IntPriorityQueueDouble
Gets the current size of the IntPriorityQueueDouble, which is the number of (element, priority) pairs that it contains. Specified by:
size
in interfaceIntPriorityQueueDouble
 Returns:
 the current size of the IntPriorityQueueDouble.
