public class Heap
extends java.lang.Object
If a maximum size is given in the constructor, then this heap will never grow beyond that size. Furthermore, if this is a max heap, then only the bottom max capacity elements will be retained in the heap. If this is a min heap, then only the top max capacity elements will be retained in the heap. The purpose of this is to allow efficient implentation of a "top n box". That is, when sorting through a large group of elements, where only the top n elements are to be stored, this can be efficiently accomplished by creating a Min Heap of max size n. This is accomplished through the add method. Without loss of generality, assume the heap is a min-heap. If the heap size is already equal to max size, then when a new element e is added through the add method, it will only be added if it is greater than the currently smallest element in the heap. If it is added, then the smallest element in the heap will be removed.
This implentation relies heavily upon the discussion of heaps in
Cormen, T., C. Leiserson, R. Rivest, and C. Stein. <i>Introduction to Algorithms, second ed.</i> Cambridge: MIT Press, 2001.
Modifier and Type | Field and Description |
---|---|
private java.util.Comparator<? super java.lang.Object> |
comp |
private int |
heapSize |
private static int |
INIT_CAPACITY |
static int |
MAX_HEAP |
private int |
maxSize |
static int |
MIN_HEAP |
private int |
sign |
private java.lang.Object[] |
theHeap |
Constructor and Description |
---|
Heap()
Creates a new Heap of type MAX_HEAP and initial capacity of INIT_CAPACITY.
|
Heap(java.util.Comparator<? super java.lang.Object> c)
Creates a new Heap of type MAX_HEAP and initial capacity of INIT_CAPACITY.
|
Heap(java.util.Comparator<? super java.lang.Object> c,
int maxCapacity)
Creates a new Heap of type MAX_HEAP and the specified initial capacity.
|
Heap(java.util.Comparator<? super java.lang.Object> c,
int maxCapacity,
int type)
Creates a new Heap of type MAX_HEAP and the specified initial capacity.
|
Heap(int type)
Creates a new Heap of the specified type and initial capacity of INIT_CAPACITY.
|
Heap(int maxCapacity,
int type)
Creates a new Heap of type MAX_HEAP and the specified initial capacity.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(java.lang.Object o)
Adds the object to the heap.
|
int |
capacity()
Returns the size of this heap's array, and so how many elements it can hold before it will be expanded.
|
void |
clear()
Empties the heap and returns the capacity to the max capacity, if specified, or the INIT_CAPACITY.
|
private int |
compare(java.lang.Object o1,
java.lang.Object o2)
Functions like the comparator's compare method.
|
private void |
exchange(int i,
int j)
Simply exchanges the objects at indeces i and j.
|
java.lang.Object |
extractTop()
Removes the top object off the heap and returns it.
|
java.lang.Object |
getTop()
Returns the top of the heap.
|
private void |
heapify(int i)
Given a node i, assumes that left(i) and right(i) are roots of proper heaps, but that the heap rooted at i may not be.
|
boolean |
isEmpty()
Returns true if there are no elements in the heap.
|
private int |
left(int i) |
int |
maxCapacity()
The maximum allowable size for this Heap.
|
private int |
parent(int i) |
private int |
right(int i) |
int |
size()
Returns the current number of objects in this heap.
|
java.lang.Object[] |
toArray()
Returns a shallow copy of the heap as an array.
|
java.lang.Object[] |
toArray(java.lang.Object[] a)
Like
toArray() , but the runtime type of the returned array is that of the specified array. |
java.lang.Object[] |
toSortedArray()
Same as toArray, but returns it in sorted order.
|
java.lang.Object[] |
toSortedArray(java.lang.Object[] a)
Like
toSortedArray() , but the runtime type of the returned array is that of the specified array. |
private static final int INIT_CAPACITY
public static final int MAX_HEAP
public static final int MIN_HEAP
private java.util.Comparator<? super java.lang.Object> comp
private int heapSize
private int maxSize
private int sign
private java.lang.Object[] theHeap
public Heap()
public Heap(java.util.Comparator<? super java.lang.Object> c)
public Heap(java.util.Comparator<? super java.lang.Object> c, int maxCapacity)
public Heap(java.util.Comparator<? super java.lang.Object> c, int maxCapacity, int type)
public Heap(int type)
public Heap(int maxCapacity, int type)
public boolean add(java.lang.Object o)
Operates in O(log n) time, where n is the number of elements in the heap.
public int capacity()
public void clear()
private int compare(java.lang.Object o1, java.lang.Object o2)
private void exchange(int i, int j)
public java.lang.Object extractTop() throws java.util.NoSuchElementException
java.util.NoSuchElementException
public java.lang.Object getTop()
private void heapify(int i)
Runs in O(log n) time.
public boolean isEmpty()
private int left(int i)
public int maxCapacity()
private int parent(int i)
private int right(int i)
public int size()
public java.lang.Object[] toArray()
public java.lang.Object[] toArray(java.lang.Object[] a)
toArray()
, but the runtime type of the returned array is that of the specified array.public java.lang.Object[] toSortedArray()
public java.lang.Object[] toSortedArray(java.lang.Object[] a)
toSortedArray()
, but the runtime type of the returned array is that of the specified array.