swift-collections icon indicating copy to clipboard operation
swift-collections copied to clipboard

[Heap] Change value of minimum or maximum element

Open CTMacUser opened this issue 2 years ago • 2 comments

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.

CTMacUser avatar Oct 11 '21 00:10 CTMacUser

The replaceMin and replaceMax 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.)

CTMacUser avatar Oct 12 '21 09:10 CTMacUser

@swift-ci test

lorentey avatar Nov 22 '21 21:11 lorentey

Merged with changes in #208

lorentey avatar Oct 12 '22 23:10 lorentey