v2.0.0
Breaking Updates
-
Remove dump() from the Heap
The original idea was for the default iterator on Sorted objects
to iterate the object in sorted order. When order did not matter, dump()
could be used.In practice, there exists objects that are considered sorted in usage but
not in implementation. Heaps are an example of this; to return elements in
sorted order, extra work is required. If this is the behavior of the
default iterator, then this work is done implicitly. This can become a penalty
as an object is passed to contexts where this behavior is not known.This update removes this constraint on the default iterator. It no longer must return a
elements in sorted order (though it is of course free to do so). Objects should instead
provide a separate method for in-order traversal of their elements (such as Heap.sorted()).
Features:
- Add Tree interface
- Add SortedTree interface
- Add AATree implementation
Enhancement
-
Improve performance of skewMerge() used by SkewHeap
skewMerge() merges K leftist heaps into 1. The process involves potentially splitting each
heap into multiple heaps, then combining all of them. The total number of heaps after splitting is N.The previous implementation did this in Nlog(N) time complexity. The new implementation uses a heapSort
approach to do this in Nlog(K) time complexity (see mergeKSorted() in src/heap/utils).