DoubleRadixAddressableHeap (JHeaps)

java.lang.Object
- org.jheaps.monotone.DoubleRadixAddressableHeap<V>

Type Parameters:

V - the type of values maintained by this heap

All Implemented Interfaces:

Serializable, AddressableHeap<Double,V>
```
public class DoubleRadixAddressableHeap<V>
extends Object
```
An addressable radix heap for double keys. The heap stores double keys sorted according to the natural ordering of its keys. A radix heap is a monotone heap, especially designed for algorithms (such as Dijkstra) which scan elements in order of nondecreasing keys.
Note that this implementation uses the fact that the IEEE floating-point standard has the property that for any valid floating-point numbers a and b, a<=b if and only if bits(a)<= bits(b), where bits(x) denotes the re-interpretation of x as an unsigned integer (long in our case).
The implementation use arrays in order to store the elements. Operations insert and findMin are worst-case constant time. The cost of operation deleteMin is amortized O(logC) assuming the radix-heap contains keys in the range [0, C] or equivalently [a,a+C]. Note, however, that C here depends on the distance of the minimum and maximum value when they are translated into unsigned longs.
Note that this implementation is not synchronized. If multiple threads access a heap concurrently, and at least one of the threads modifies the heap structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements or changing the key of some element.) This is typically accomplished by synchronizing on some object that naturally encapsulates the heap.

Author:

Dimitrios Michail

See Also:

Serializable, Serialized Form

Nested Class Summary
- Nested classes/interfaces inherited from interface org.jheaps.AddressableHeap
  AddressableHeap.Handle<K,V>

Constructor Summary

Constructors
Constructor and Description
`DoubleRadixAddressableHeap(double minKey, double maxKey)` Constructs a new heap which can store values between a minimum and a maximum key value (inclusive).

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clear()` Clear all the elements of the heap.
`Comparator<? super K>`	`comparator()` Always returns `null` since this heap uses the natural ordering of its keys.
`AddressableHeap.Handle<K,V>`	`deleteMin()` Delete and return an element with the minimum key.
`AddressableHeap.Handle<K,V>`	`findMin()` Find an element with the minimum key.
`AddressableHeap.Handle<K,V>`	`insert(K key)` Insert a new element into the heap with a null value.
`AddressableHeap.Handle<K,V>`	`insert(K key, V value)` Insert a new element into the heap.
`boolean`	`isEmpty()` Returns `true` if this heap is empty.
`long`	`size()` Returns the number of elements in the heap.

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - DoubleRadixAddressableHeap
```
public DoubleRadixAddressableHeap(double minKey,
                                  double maxKey)
```
    Constructs a new heap which can store values between a minimum and a maximum key value (inclusive). It is important to use the smallest key range as the heap uses O(logC) where C=maxKey-minKey+1 buckets to store elements. Moreover, the operation deleteMin requires amortized O(logC) time.
    
    Parameters:
    
    minKey - the non-negative minimum key that this heap supports (inclusive)
    
    maxKey - the maximum key that this heap supports (inclusive)
    
    Throws:
    
    IllegalArgumentException - if the minimum key is negative
    
    IllegalArgumentException - if the maximum key is less than the minimum key
- Method Detail
  - findMin
```
public AddressableHeap.Handle<K,V> findMin()
```
    Find an element with the minimum key.
    
    Specified by:
    
    findMin in interface AddressableHeap<K,V>
    
    Returns:
    
    a handle to an element with minimum key
  - insert
```
public AddressableHeap.Handle<K,V> insert(K key)
```
    Insert a new element into the heap with a null value.
    
    Specified by:
    
    insert in interface AddressableHeap<K,V>
    
    Parameters:
    
    key - the element's key
    
    Returns:
    
    a handle for the newly added element
    
    Throws:
    
    IllegalArgumentException - if the key is null
    
    IllegalArgumentException - if the key is less than the minimum allowed key
    
    IllegalArgumentException - if the key is more than the maximum allowed key
    
    IllegalArgumentException - if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
  - insert
```
public AddressableHeap.Handle<K,V> insert(K key,
                                          V value)
```
    Insert a new element into the heap.
    
    Specified by:
    
    insert in interface AddressableHeap<K,V>
    
    Parameters:
    
    key - the element's key
    
    value - the element's value
    
    Returns:
    
    a handle for the newly added element
    
    Throws:
    
    IllegalArgumentException - if the key is null
    
    IllegalArgumentException - if the key is less than the minimum allowed key
    
    IllegalArgumentException - if the key is more than the maximum allowed key
    
    IllegalArgumentException - if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
  - deleteMin
```
public AddressableHeap.Handle<K,V> deleteMin()
```
    Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only method AddressableHeap.Handle.getKey() and AddressableHeap.Handle.getValue() can be used. The cost of this operation is amortized O(logC) assuming the heap contains keys in the range [0, C] or equivalently [a, a+C].
    
    Specified by:
    
    deleteMin in interface AddressableHeap<K,V>
    
    Returns:
    
    a handle to the deleted element with minimum key
  - isEmpty
```
public boolean isEmpty()
```
    Returns true if this heap is empty.
    
    Specified by:
    
    isEmpty in interface AddressableHeap<K,V>
    
    Returns:
    
    true if this heap is empty, false otherwise
  - size
```
public long size()
```
    Returns the number of elements in the heap.
    
    Specified by:
    
    size in interface AddressableHeap<K,V>
    
    Returns:
    
    the number of elements in the heap
  - clear
```
public void clear()
```
    Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methods AddressableHeap.Handle.decreaseKey(Object) and AddressableHeap.Handle.delete() is undefined.
    
    Specified by:
    
    clear in interface AddressableHeap<K,V>
  - comparator
```
public Comparator<? super K> comparator()
```
    Always returns null since this heap uses the natural ordering of its keys.
    
    Specified by:
    
    comparator in interface AddressableHeap<K,V>
    
    Returns:
    
    null since this heap uses the natural ordering of its keys

Class DoubleRadixAddressableHeap<V>

Nested Class Summary

Nested classes/interfaces inherited from interface org.jheaps.AddressableHeap

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

DoubleRadixAddressableHeap

Method Detail

findMin

insert

insert

deleteMin

isEmpty

size

clear

comparator