Skip to content

v2.0.0

Compare
Choose a tag to compare
@havelessbemore havelessbemore released this 24 May 07:46
· 43 commits to main since this release

Breaking Updates

  1. 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:

  1. Add Tree interface
  2. Add SortedTree interface
  3. Add AATree implementation

Enhancement

  1. 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).