Another implicit data structure: the poplar heap

[Morwenn]

I know of at least one other implicit data structure not mentioned in your list: the poplar heap. It's actually a derivative of the binary heap with a different layout for the elements (the biggest element is stored on the right when it would be stored on the left in a regular heap structure). This new layout has first been proposed by Coenraad Bron and Wim H. Hesselink in their paper Smoothsort revisited, but for some reason they decided to store an array of indices that takes O(log n) space. I noticed that we could get rid of the array and still keep the complexity of the different heap operations as is; nothing ground breaking but that makes a poplar heap a different implicit data structure.

I have a repository where I started to write about it since I couldn't find information anywhere, but since the implicit data structure isn't really interesting per se I never finished the write-up :/

I might try to finish the write-up someday for the sake of it.

[pfalcon]

Thanks for the notice and links, much appreciated! Please let me do some homework on this structure and I'll be happy to add it to this repo.

but since the implicit data structure isn't really interesting per se I never finished the write-up :/

I agree that in there current state of affairs in IT, the implicit data structures are niche phenomena. But that means that many people don't even know that there's a whole class of such structures (not just the binary heap), so collecting info together might help find still niche, but interesting uses for them.

[Morwenn]

Good luck finding any documentation for the homework. The specific layout of the poplar heap is only described in Smoothsort Revisited as far a I know, which is only available if you can access old papers from Elsevier. Even then it used O(log n) space and thus wasn't implicit. On the other hand if you find any other resource explaining the algorithm, I'll gladly welcome it :p

I created the other repository to make the original algorithm more understandable (also to have a wiely available explanation), and show how to turn poplar heap into an implicit data structure with operations that also use O(1) space. I finished the coding part of the project, but explaining stuff is hard so I'm rather slow...

[Morwenn]

That was faster than I thought, but I'm more or less done describing both the original algorithm and how to turn poplar heap into an implicit data structure. I'm in the middle of testing the code examples again and polishing the description, but essentially everything is here.

Don't hesite to comment if you find things hard to understand or if you sport an issue :)

EDIT: and it's done, all the code works after a few minor corrections.

[Morwenn]

I found another paper describing the same data structure but under the name post-order heap: https://people.csail.mit.edu/nickh/Publications/PostOrderHeap/FUN04-PostOrderHeap.pdf

The data structure is the same, the algorithms to build the heap and to remove elements from it build on common bases too, even though our tricks to compute the indices aren't exactly the same.

EDIT: the post-order heap needs to store two additional integers for its algorithms to work, while the algorithms I used in the poplar heap project only need the collection of elements and its size.

[pfalcon]

Hi @Morwenn, thanks for sharing updates! Sorry, but I completely forgot about this ticket, then also got sidetracked when seeing your recent comment. And well, I'm still to busy with other things to work thru it beyond posting this comment. But I hope to get back to it ;-).

[Morwenn]

It's ok, I've got my whole life before me :p

If you're interested I found a few papers on arXiv mentioning other implicit data structures, even though they probably haven't been implemented outside of research.

[pfalcon]

Sure, if you'd have some time to post them in a separate ticket, that would be appreciated by me and other folks who may come by.

[pfalcon]

As shameful as it is for taking so much time to be added, both Poplar and Post-order heaps are now in: https://github.com/pfalcon/awesome-implicit-data-structures/commit/ea1851e94072e703dfc8c156cca38c1fb170d7c6 . Thanks @Morwenn for both bringing it up, and working on poplar heap implementation!