Package org.graph4j.util

Class VertexHeap

java.lang.Object

org.graph4j.util.VertexHeap

All Implemented Interfaces:

Iterable<Integer>

public class VertexHeap
extends Object
implements Iterable<Integer>

Implementation of a binary min heap using arrays. The keys stored in the heap represent the vertex indices of a graph, from 0 to numVertices() - 1. The order relation is given by a comparator.

Author:

Cristian Frăsinaru

Constructor Summary

Constructors

Constructor	Description
VertexHeap(Graph graph, boolean addAll, IntComparator comparator)
VertexHeap(Graph graph, IntComparator comparator)

Method Summary

Modifier and Type	Method	Description
final void	add(int key)
boolean	addOrUpdate(int key)
boolean	contains(int key)
boolean	isEmpty()
Iterator<Integer>	iterator()
int[]	keys()
int	peek()
int	poll()	Returns and removes the minimum.
boolean	remove(int key)	Removes a specified key from the heap.
int	size()
String	toString()
boolean	update(int key)

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

VertexHeap

public VertexHeap(Graph graph,
 IntComparator comparator)

Parameters:

graph - the graph the vertices of the heap belong to.

comparator - a comparator for vertices.

VertexHeap

public VertexHeap(Graph graph,
 boolean addAll,
 IntComparator comparator)

Parameters:

graph - the graph the vertices of the heap belong to.

addAll - add all graph vertices in the heap.

comparator - a comparator for vertices.

Method Details

size

public int size()

Returns:

the number of vertices in the heap.

isEmpty

public boolean isEmpty()

Returns:

true if the heap contains no vertices.

keys

public int[] keys()

Returns:

a new array containing the keys in the heap.

iterator

public Iterator<Integer> iterator()

Specified by:

iterator in interface Iterable<Integer>

Returns:

an iterator over the vertices in the heap.

contains

public boolean contains(int key)

Parameters:

key - a vertex index.

Returns:

true if the key is contained in the heap.

add

public final void add(int key)

Parameters:

key - a vertex index.

peek

public int peek()

Returns:

the key (index) corresponding to the minimum value.

poll

public int poll()

Returns and removes the minimum.

Returns:

the key (index) corresponding to the minimum value.

remove

public boolean remove(int key)

Removes a specified key from the heap.

Parameters:

key - the index of a vertex.

Returns:

true if the heap has changed.

update

public boolean update(int key)

Parameters:

key - the index of a vertex.

Returns:

true if the heap has changed.

addOrUpdate

public boolean addOrUpdate(int key)

Parameters:

key - the index of a vertex.

Returns:

true if the heap has changed.

toString

public String toString()

Overrides:

toString in class Object