E
- Element type. Should be Comparable
or a
Comparator
needs to be given.public class Heap<E> extends AbstractQueue<E> implements Serializable
PriorityQueue
, but here we can override methods to obtain
e.g. a TopBoundedHeap
Additionally, this heap is built lazily: if you first add many elements, then
poll the heap, it will be bulk-loaded in O(n) instead of iteratively built in
O(n log n). This is implemented via a simple validTo counter.Modifier and Type | Class and Description |
---|---|
protected class |
Heap.Itr
Iterator over queue elements.
|
Modifier and Type | Field and Description |
---|---|
protected Comparator<Object> |
comparator
The comparator or
null |
private static int |
DEFAULT_INITIAL_CAPACITY
Default initial capacity
|
int |
modCount
(Structural) modification counter.
|
protected Object[] |
queue
Heap storage
|
private static long |
serialVersionUID
Serial version
|
protected int |
size
Current number of objects
|
protected int |
validSize
Indicate up to where the heap is valid
|
Constructor and Description |
---|
Heap()
Default constructor: default capacity, natural ordering.
|
Heap(Comparator<? super E> comparator)
Constructor with
Comparator . |
Heap(int size)
Constructor with initial capacity, natural ordering.
|
Heap(int size,
Comparator<? super E> comparator)
Constructor with initial capacity and
Comparator . |
Modifier and Type | Method and Description |
---|---|
boolean |
add(E e) |
boolean |
addAll(Collection<? extends E> c) |
protected E |
castQueueElement(int n) |
protected String |
checkHeap()
Test whether the heap is still valid.
|
void |
clear() |
boolean |
contains(Object o) |
protected void |
ensureValid()
Repair the heap
|
protected boolean |
heapifyDown(int pos,
Object reinsert)
Execute a "Heapify Downwards" aka "SiftDown".
|
protected boolean |
heapifyDownComparable(int ipos,
Object reinsert)
Execute a "Heapify Downwards" aka "SiftDown".
|
protected boolean |
heapifyDownComparator(int ipos,
Object cur)
Execute a "Heapify Downwards" aka "SiftDown".
|
protected void |
heapifyUp(int pos,
E elem)
Execute a "Heapify Upwards" aka "SiftUp".
|
protected void |
heapifyUpComparable(int pos,
Object elem)
Execute a "Heapify Upwards" aka "SiftUp".
|
protected void |
heapifyUpComparator(int pos,
Object cur)
Execute a "Heapify Upwards" aka "SiftUp".
|
Iterator<E> |
iterator() |
boolean |
offer(E e) |
E |
peek() |
E |
poll() |
protected E |
removeAt(int pos)
Remove the element at the given position.
|
protected void |
resize(int requiredSize)
Test whether we need to resize to have the requested capacity.
|
int |
size() |
ArrayList<E> |
toSortedArrayList()
Return the heap as a sorted array list, by repeated polling.
|
element, remove
containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray
private static final long serialVersionUID
protected transient Object[] queue
protected int size
protected int validSize
protected final Comparator<Object> comparator
null
public transient int modCount
private static final int DEFAULT_INITIAL_CAPACITY
public Heap()
public Heap(int size)
size
- initial sizepublic Heap(Comparator<? super E> comparator)
Comparator
.comparator
- Comparatorpublic Heap(int size, Comparator<? super E> comparator)
Comparator
.size
- initial capacitycomparator
- Comparatorpublic boolean add(E e)
add
in interface Collection<E>
add
in interface Queue<E>
add
in class AbstractQueue<E>
protected void ensureValid()
protected E removeAt(int pos)
pos
- Element position.protected void heapifyUp(int pos, E elem)
pos
- insertion positionelem
- Element to insertprotected void heapifyUpComparable(int pos, Object elem)
pos
- insertion positionelem
- Element to insertprotected void heapifyUpComparator(int pos, Object cur)
pos
- insertion positioncur
- Element to insertprotected boolean heapifyDown(int pos, Object reinsert)
pos
- re-insertion positionreinsert
- Object to reinsertprotected boolean heapifyDownComparable(int ipos, Object reinsert)
ipos
- re-insertion positionprotected boolean heapifyDownComparator(int ipos, Object cur)
ipos
- re-insertion positionprotected final E castQueueElement(int n)
public int size()
size
in interface Collection<E>
size
in class AbstractCollection<E>
protected final void resize(int requiredSize)
requiredSize
- required capacitypublic void clear()
clear
in interface Collection<E>
clear
in class AbstractQueue<E>
public boolean contains(Object o)
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
public Iterator<E> iterator()
iterator
in interface Iterable<E>
iterator
in interface Collection<E>
iterator
in class AbstractCollection<E>
public boolean addAll(Collection<? extends E> c)
addAll
in interface Collection<E>
addAll
in class AbstractQueue<E>
public ArrayList<E> toSortedArrayList()
protected String checkHeap()
null
when the heap is correct