apple / swift-algorithms

Commonly used sequence and collection algorithms for Swift
Apache License 2.0
5.97k stars 443 forks source link

Added a heap view to Collection that manages a simple Heap structure #14

Closed dfsweeney closed 4 years ago

dfsweeney commented 4 years ago

Added Heap to provide a comparator-based in-order view of a Collection.

I know @rakaramos has been working on this with PartialSort and some other things that are more in line with the evolution process. So this is kind of a foul but I put this together to scratch an itch and wanted to sent the PR for people to look at.

I used the Permutations code as a base. There's been some discussion of algorithms vs data structures in the forums. This is a weird one because it includes a data structure to support a partial sort algorithm.

I'm also not sure if there is not a "currency type" hiding in there around the array of indexes that is also treated as a binary tree. C++ has some methods in algorithm that let you treat an array as a binary tree, and the heap algorithms do something like that.

I put some other notes in Guides/Heap.md as well. There are still some to-dos at the top of Heap.swift.

Thanks for looking at this!

Checklist

natecook1000 commented 4 years ago

Thanks for this contribution, @dfsweeney. You're right that the Heap data structure belongs in a different package than Algorithms. I'm going to close this PR — please feel free to start a thread in the forums if you'd like to continue the discussion.

My hunch is that you'll ultimately end up with a better data structure actually storing the elements in the internal array, rather than the indices. This kind of wrapper works best when it isn't making any extra allocations, but since you have to copy the indices, you might as well copy the elements instead. Storing the elements would let you implement the other half of the heap operations, as well.