I will shamelessly offer my package TrackingHeaps as an alternative. However, I am forced to point out it is very similar to the DataStructures.MutableBinaryHeap. See this discussion for the differences. Both structures use vectors inside them and allow support sizehint! (however, they just delegate the sizehint! to the internal Vectors and I think Base makes no guarantees about how it works).
I think @lmiq suggestion about linked lists is a little off. Your description of what you want is basically the textbook definition of a heap/‘priority queue’ implemented with a vector/array plus a tracking system to be able to make changes anywhere in the tree. However, the fact that you have thousands of very small heaps may open the possibility of alternative solutions. Such small heaps will live in entirely in the register (or in the L1 cache) if implemented with vectors, so this is a must. Depending on your specifics (if you have memory for allocating the worst-case size of each heap and is losing much time with allocation and loss of locality), then maybe allocating a huge vector (as @lmiq suggested) and treating each 20 elements range as a different heap (using nothing for empty spaces or keeping their sizes in another vector) may be a good solution, but it is very low level and will be hard to work with.