mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
* Add PriorityQueue implementation built on top of a MinMaxHeap * Merge MinMaxHeap into PriorityQueue * Add `unordered` read-only view into underlying heap * Start filling in PriorityQueue benchmarks * Implement our own swapAt() storage.swapAt exhibits excessive allocations * Rename _delete(at:) to _remove(at:) * Rename removeMin/removeMax -> popMin/popMax * Use magic values 1, 2 to refer to the items in the first max level Co-authored-by: Tim Vermeulen <tvermeulen@apple.com> * Specify logarithmic complexities as "O(log `count`) / 2" instead of "O(log n)" Co-authored-by: Tim Vermeulen <tvermeulen@apple.com> * Clarify logic in popMax * Simplify logic in _remove(at:) * Move the bounds checking into the various index computation methods They will all now return `nil` for invalid indices. * Floyd's heap construction algorithm should start from count/2 - 1 * Add ObjC wrapper around CFBinaryHeap to benchmarks * Fix benchmarks that broke because of renames * Add removeMin/removeMax * Make _minMaxHeapIsMinLevel an instance method * Split _indexOfChildOrGrandchild(of:sortedUsing:) into two separate functions There is a large performance cost with passing a predicate function. * Defer comparing children when determining largest/smallest descendant If the given index has 4 grandchildren, we can skip comparing the children. * Added an iterator of the min and max views to the priority queue * seperated iterator implementation into a new file * Use renamed popMin/Max in Iterator instead of removeMin/Max * Fix code formatting Indentation of 2 spaces and 80 char column width * Add sequence initializer * Fix code formatting in benchmarks * Fix benchmark names * Remove init from Collection This should already be handled by the init from Sequence * Add conformance to ExpressibleByArrayLiteral * Move ExpressibleByArrayLiteral conformance to separate file * Update PriorityQueue's CMakeLists.txt * Make ascending and descending iterators public * Inline ALL THE THINGS! * Iterative instead of recursive implementation, @inline(__always) a couple more critical functions. * Address PR feedback, thanks! * Check invariants on insertion and deletion * Minor code formatting cleanup * Add copyright header to test file * Fix missing empty line * Add naïve implementation of insert(contentsOf:) * Add documentation on complexity of init<S:Sequence>(_:) * Cite source paper in documentation * Rename PriorityQueue -> MinMaxHeap We'll be reintroducing the PriorityQueue type as a wrapper. * Mark insert(contentsOf:) as inlinable This results in ~10x speedup in my initial tests. * Rename argument label "startingAt" -> "elementAt" These functions used to be recursive, so "startingAt" made sense. Now that they're iterative, we should fix the label. * Remove coefficients from complexity docs * Make `_minMaxHeapIsMinLevel` take an index instead of a count * Rename MinMaxHeap -> Heap * Add documentation for Heap * Make Heap.Iterator init and direction internal * Fix reference to queue in documentation Co-authored-by: Dante Broggi <34220985+Dante-Broggi@users.noreply.github.com> * Don't wrap integers in CFBinaryHeap benchmark in NSNumber * Avoid heap allocation altogether * Add table with performance of operations * Add heap performance graph * Apply suggestions from code review Co-authored-by: Karoy Lorentey <klorentey@apple.com> * Make _checkInvariants comments a doc comment * Split Heap.Iterator into two separate views Adapted from Daryle Walker's (github.com/CTMacUser) suggestions * Prefix heap storage variable with an underscore * Update benchmark image * Fix Sources/PriorityQueueModule/CMakeLists.txt Heap+Iterator.swift was renamed to Heap+OrderedViews.swift Co-authored-by: Karoy Lorentey <klorentey@apple.com> * CFBinaryHeap is only available on Darwin * CFBinaryHeap is only available on Darwin * CFBinaryHeap is only available on Darwin Co-authored-by: Tim Vermeulen <tvermeulen@apple.com> Co-authored-by: Amanuel Ephem <amanuelephrem776@gmail.com> Co-authored-by: Joakim Hassila <joj@mac.com> Co-authored-by: Dante Broggi <34220985+Dante-Broggi@users.noreply.github.com> Co-authored-by: Karoy Lorentey <klorentey@apple.com>