swift-collections
swift-collections copied to clipboard
[Heap] Change value of minimum or maximum element
Adds two methods to change either the minimum or maximum element of a Heap
instance. If the value changes enough that the previous second-place element now surpasses it, that former second-place element will take over for the heap's min/max element.
For testing purposes, I needed a way to precisely define a heap's pre-test state. Therefore, I also added a new initializer that receives an exact storage layout as input. It's a fail-able initializer. This requires a testing function. There is such a procedure locked in the debug-only invariant code. I moved that code to a new unconditional method that both the new initializer and the invariant-test code both reference.
Checklist
- [x] I've read the Contribution Guidelines
- [x] My contributions are licensed under the Swift license.
- [x] I've followed the coding style of the rest of the project.
- [x] I've added tests covering all new code paths my change adds to the project (if appropriate).
- [ ] I've added benchmarks covering new functionality (if appropriate).
- [ ] I've verified that my change does not break any existing tests or introduce unexplained benchmark regressions.
- [ ] I've updated the documentation if necessary.
The
replaceMin
andreplaceMax
members look like good additions to me. BTW, do you have motivating example for adding these? It's not immediately obvious to me that these operations would often come handy in practice. (It would also be nice to list heap implementations in other languages that provide similar operations.)
This was one of the future directions from the original Heap
authors. It makes sense because naïve replacement via a pop
and push
unnecessarily does two rounds of element shuffling instead of one. (And maybe a reallocation too.)
@swift-ci test
Merged with changes in #208