Package smile.util

Class PairingHeap<E extends Comparable<E>>

java.lang.Object

smile.util.PairingHeap<E>

All Implemented Interfaces:

Iterable<E>, Collection<E>, Queue<E>

public class PairingHeap<E extends Comparable<E>>
extends Object
implements Queue<E>

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a robust choice for implementing such algorithms as Prim's MST algorithm.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	PairingHeap.Node	A multiway tree node in the pairing heap.

Constructor Summary

Constructors

Constructor	Description
PairingHeap()

Method Summary

Modifier and Type	Method	Description
boolean	add(E value)
boolean	addAll(Collection<? extends E> c)
PairingHeap<E>.Node	addNode(E value)	Adds a new element to the pairing heap.
void	clear()
boolean	contains(Object o)
boolean	containsAll(Collection<?> c)
E	element()
boolean	isEmpty()
Iterator<E>	iterator()
boolean	offer(E value)
E	peek()
E	poll()
void	rebuild()	Rebuilds the pairing heap.
E	remove()
boolean	remove(Object o)
boolean	removeAll(Collection<?> c)
boolean	retainAll(Collection<?> c)
int	size()
Object[]	toArray()
<T> T[]	toArray(T[] a)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Details

PairingHeap

public PairingHeap()

Method Details

size

public int size()

Specified by:

size in interface Collection<E extends Comparable<E>>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<E extends Comparable<E>>

addNode

public PairingHeap<E>.Node addNode(E value)

Adds a new element to the pairing heap.

Parameters:

value - a new element.

Returns:

a Node corresponding to the newly added element.

rebuild

public void rebuild()

Rebuilds the pairing heap. Assumes that all elements inside the pairing heap are out of order due to side-channel updates.

add

public boolean add(E value)

Specified by:

add in interface Collection<E extends Comparable<E>>

Specified by:

add in interface Queue<E extends Comparable<E>>

offer

public boolean offer(E value)

Specified by:

offer in interface Queue<E extends Comparable<E>>

peek

public E peek()

Specified by:

peek in interface Queue<E extends Comparable<E>>

element

public E element()

Specified by:

element in interface Queue<E extends Comparable<E>>

poll

public E poll()

Specified by:

poll in interface Queue<E extends Comparable<E>>

remove

public E remove()

Specified by:

remove in interface Queue<E extends Comparable<E>>

clear

public void clear()

Specified by:

clear in interface Collection<E extends Comparable<E>>

addAll

public boolean addAll(Collection<? extends E> c)

Specified by:

addAll in interface Collection<E extends Comparable<E>>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<E extends Comparable<E>>

containsAll

public boolean containsAll(Collection<?> c)

Specified by:

containsAll in interface Collection<E extends Comparable<E>>

retainAll

public boolean retainAll(Collection<?> c)

Specified by:

retainAll in interface Collection<E extends Comparable<E>>

removeAll

public boolean removeAll(Collection<?> c)

Specified by:

removeAll in interface Collection<E extends Comparable<E>>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<E extends Comparable<E>>

toArray

public Object[] toArray()

Specified by:

toArray in interface Collection<E extends Comparable<E>>

toArray

public <T> T[] toArray(T[] a)

Specified by:

toArray in interface Collection<E extends Comparable<E>>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Collection<E extends Comparable<E>>

Specified by:

iterator in interface Iterable<E extends Comparable<E>>