squidpony.squidmath

Class BinaryHeap<T extends BinaryHeap.Node>

java.lang.Object

squidpony.squidmath.BinaryHeap<T>

public class BinaryHeap<T extends BinaryHeap.Node>
extends java.lang.Object

A binary heap that stores nodes which each have a double value and are sorted either lowest first or highest first. The BinaryHeap.Node class can be extended to store additional information.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BinaryHeap.Node A binary heap node.

Field Summary

Fields

Modifier and Type	Field and Description
int	size

Constructor Summary

Constructors

Constructor and Description
BinaryHeap()
BinaryHeap(int capacity, boolean isMaxHeap)

Method Summary

Modifier and Type	Method and Description
T	add(T node) Adds the node to the heap using its current value.
T	add(T node, double value) Sets the node's value and adds it to the heap.
void	clear()
boolean	contains(T node, boolean identity) Returns true if the heap contains the specified node.
boolean	equals(java.lang.Object obj)
int	hashCode()
boolean	isEmpty() Returns true if the heap is empty.
boolean	notEmpty() Returns true if the heap has one or more items.
T	peek() Returns the first item in the heap.
T	pop() Removes the first item in the heap and returns it.
T	remove(T node)
void	setValue(T node, double value) Changes the value of the node, which should already be in the heap.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

size

public int size

Constructor Detail

BinaryHeap

public BinaryHeap()

BinaryHeap

public BinaryHeap(int capacity,
                  boolean isMaxHeap)

Method Detail

add

public T add(T node)

Adds the node to the heap using its current value. The node should not already be in the heap.

add

public T add(T node,
             double value)

Sets the node's value and adds it to the heap. The node should not already be in the heap.

contains

public boolean contains(T node,
                        boolean identity)

Returns true if the heap contains the specified node.

Parameters:

identity - If true, == comparison will be used. If false, .equals() comparison will be used.

peek

public T peek()

Returns the first item in the heap. This is the item with the lowest value (or highest value if this heap is configured as a max heap).

pop

public T pop()

Removes the first item in the heap and returns it. This is the item with the lowest value (or highest value if this heap is configured as a max heap).

remove

public T remove(T node)

notEmpty

public boolean notEmpty()

Returns true if the heap has one or more items.

isEmpty

public boolean isEmpty()

Returns true if the heap is empty.

clear

public void clear()

setValue

public void setValue(T node,
                     double value)

Changes the value of the node, which should already be in the heap.

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object