I’m looking for a data structure that can insert, delete and mutate (given key) in order log n, and look at the max element in order 1.

This is either a SortedDict or one of the trees in DataStructures.jl. My issue is that those always (?) seem to allocate on insertion, which leads me to believe that they’re implemented as a node with key, value, and pointer to other nodes.

Instead, my use case is that I know that “most of the times” this tree will have of order 10 elements, and I would rather allocate an array of size 20, leave it mostly empty, and allocate more only if/when needed. Googling around I think this is called an “array implementation of a binary tree”. This http://mishadoff.com/blog/dfs-on-binary-tree-array/ looks to have all the information I need to implement it myself, but if someone has already done it, even better!

Does any of this make sense? And if so, does anyone know of such an implementation in Julia?