Files
940c963bc4 Add a min-max heap implementation that can be used to back a priority queue (#61)
* 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>
2021-08-06 22:21:23 -07:00
..