V - the type of values maintained by this heappublic class BinaryArrayIntegerValueHeap<V> extends Object implements ValueHeap<Integer,V>, Serializable
This is a highly optimized implementation which uses (a) the Wegener
bottom-up heuristic and (b) sentinel values. The implementation uses an array
in order to store the elements, providing amortized O(log(n)) time for the
insert and deleteMin operations. Operation findMin,
is a worst-case O(1) operation. All bounds are worst-case if the user
initializes the heap with a capacity larger or equal to the total number of
elements that are going to be inserted into the heap.
See the following papers for details about the optimizations:
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.
| Modifier and Type | Field and Description |
|---|---|
static int |
DEFAULT_HEAP_CAPACITY
Default initial capacity of the heap.
|
| Constructor and Description |
|---|
BinaryArrayIntegerValueHeap()
Constructs a new, empty heap, using the natural ordering of its keys.
|
BinaryArrayIntegerValueHeap(int capacity)
Constructs a new, empty heap, with a provided initial capacity using the
natural ordering of its keys.
|
| Modifier and Type | Method and Description |
|---|---|
void |
clear()
Clear all the elements of this heap.
|
Comparator<? super Integer> |
comparator()
Returns the comparator used to order the keys in this heap, or
null if this heap uses the natural
ordering of its keys. |
Integer |
deleteMin()
Delete and return an element with the minimum key.
|
Integer |
findMin()
Find an element with the minimum key.
|
V |
findMinValue()
Find the value of an element with the minimum key.
|
void |
insert(Integer key)
Insert a key into the heap.
|
void |
insert(Integer key,
V value)
Insert an element into the heap.
|
boolean |
isEmpty()
Returns
true if this heap is empty. |
long |
size()
Returns the number of elements in this heap.
|
public static final int DEFAULT_HEAP_CAPACITY
public BinaryArrayIntegerValueHeap()
The initial capacity of the heap is DEFAULT_HEAP_CAPACITY and
adjusts automatically based on the sequence of insertions and deletions.
public BinaryArrayIntegerValueHeap(int capacity)
The initial capacity of the heap is provided by the user and is adjusted automatically based on the sequence of insertions and deletions. The capacity will never become smaller than the initial requested capacity.
capacity - the initial heap capacitypublic boolean isEmpty()
true if this heap is empty.public long size()
public void clear()
public Comparator<? super Integer> comparator()
null if this heap uses the natural
ordering of its keys.comparator in interface Heap<Integer>null if this heap uses the natural ordering of its keyspublic Integer findMin()
public V findMinValue()
findMinValue in interface ValueHeap<Integer,V>public void insert(Integer key)
Copyright © 2018. All rights reserved.