A heap is a special kind of binary tree in which every node is greater than all of its children
The implementation is based on an arrayed binary tree.
Example:
class Element implements polygonal.ds.Heapable<Element> {
public var id:Int;
public var position:Int;
public function new(id:Int) {
this.id = id;
}
public function compare(other:Element):Int {
return other.id - id;
}
public function toString():String {
return Std.string(id);
}
}
...
var o = new polygonal.ds.Heap<Element>();
o.add(new Element(64));
o.add(new Element(13));
o.add(new Element(1));
o.add(new Element(37));
trace(o); //outputs:
[ Heap size=4
front
0 -> 1
1 -> 13
2 -> 37
3 -> 64
]
Constructor
new (initalCapacity:Int = 1, ?source:Array<T>)
Parameters:
initialCapacity | the initial physical space for storing values. Useful before inserting a large number of elements as this reduces the amount of incremental reallocation. |
|---|---|
source | copies all values from |
Variables
read onlycapacity:Int
The size of the allocated storage space for the elements.
If more space is required to accommodate new elements, capacity grows according to this.growthRate.
The capacity never falls below the initial size defined in the constructor and is usually a bit larger than this.size (mild overallocation).
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
reuseIterator:Bool = false
If true, reuses the iterator object instead of allocating a new one when calling this.iterator().
The default is false.
If this value is true, nested iterations will fail as only one iteration is allowed at a time.
Methods
bottom ():T
Returns the item on the bottom of the heap without removing it from the heap.
This is the largest element (assuming ascending order).
change (val:T, hint:Int):Heap<T>
Rebuilds the heap in case an existing element was modified.
This is faster than removing and re-adding an element.
Parameters:
hint | a value >= 0 indicates that |
|---|
clear (gc:Bool = false):Void
Removes all elements.
Parameters:
gc | if true, elements are nullified upon removal so the garbage collector can reclaim used memory. |
|---|
clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this heap.
If byRef is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.
free ():Void
Destroys this object by explicitly nullifying all elements for GC'ing used resources.
Improves GC efficiency/performance (optional).
iterator ():Itr<T>
Returns a new HeapIterator object to iterate over all elements contained in this heap.
The values are visited in an unsorted order.
See:
pack ():Heap<T>
Reduces the capacity of the internal container to the initial capacity.
May cause a reallocation, but has no effect on this.size and its elements.
An application can use this operation to free up memory by unlocking resources for the garbage collector.
pop ():T
Removes the element on top of the heap.
This is the smallest element (assuming ascending order).
repair ():Heap<T>
Uses the Floyd algorithm (bottom-up) to repair the heap tree by restoring the heap property.
reserve (n:Int):Heap<T>
Preallocates storage for n elements.
May cause a reallocation, but has no effect on this.size and its elements.
Useful before inserting a large number of elements as this reduces the amount of incremental reallocation.
inlinetop ():T
Returns the item on top of the heap without removing it from the heap.
This is the smallest element (assuming ascending order).