Binary heap (priority queue) and heap sort in the library

[dr-m]

I believe that many applications would benefit from having something that would find the N best elements of a larger collection, as well as something that would sort a list according to a comparison predicate, like this,

[4,5,1].sort(/ a b -> a < b)

As part of arendst/Tasmota#22529 I implemented a module binary_heap.be that defines make_heap, remove_heap, and sort. I checked the internals of Berry a little, and I understood that most if not all of the built-in modules are implemented in native code. I see that the implementation of the list data structure resembles a C++ std::vector<object*>. This is great, because it facilitates a straightforward array representation of a binary heap, like the one implemented in the Berry module. It would seem to be technically feasible to implement this natively by defining a few more functions in the built-in list module. I’d be interested in such an exercise, but I would like to know how likely it would be for it to be included in Berry as well as Tasmota. I see that @s-hadinger is active in both projects.

If this idea is considered feasible, I’d welcome some suggestions regarding naming. list.sort(cmp) or list.heap_sort(cmp) would be intuitive, but list.make_heap(cmp) and list.remove_heap(cmp) could feel somewhat awkward.

[s-hadinger]

I'm a bit skeptical in the fact of embedding such libraries. Either they are simple and often too simplistic, or they try to generalize (like providing a closure for comparison) and quickly become cumbersome and much slower. In my Tasmota experience, it's better to have your own super-compact implementation that fits your need. I did this for 2 or 3 different variants of insertion sort.

[dr-m]

I understand that embedded systems are very sensitive to code bloat. If an application does not need any sorting, it would be a waste to include the code. A solution could be to implement compile-time options for selecting what to include, but then it could cause fragmentation of projects that offer pre-compiled packages. You might offer pre-compiled "lean" and "full" variants for each target that includes Berry, which would double the amount of download packages. Then, some users could start to demand further variants that are just the subset of "full" that they need. The result would be a combinatorial explosion.

Another option would be to include the binary_heap.be module in the repository as an example. Like the existing qsort.be, it could be adapted for individual applications, for example if someone wants to use a hard-coded comparison instead of a closure. In arendst/Tasmota#22529 I found a closure to work best for constructing the binary heap, because the comparison predicate requires some indirection and a special priotitization of an optional user-specified first time slot. Sorting the first cheapest times in ascending order could use a simple hard-coded <, similar to what the qsort.be does.

I see that most if not all examples include some print statements and are intended to be adapted for any specific use. Would you accept a pull request that would create a separate modules or examples/modules directory that would contain Berry modules that are intended to be ready to use as is?

[s-hadinger]

Indeed I'm more in favor of adding it to examples.
Yes we would accept such pull request

[dr-m]

I filed #459 for this. Side note: I like the CMake based build system.