I've made a container which functions like a Binary Heap in terms of insertions and popping the root element. The key difference is that the comparison steps are all replaced with a random call for deciding when to go left/right. (The underlying data structure is a Vector, written as an expandable array, so you don't need to know how many elements the heap will contain in advance.) The idea is, you can insert items, and when you pop them, you'll get any element at random. You can also iterate through the whole collection, after which the heap is reshuffled (by simply popping and reinserting N times).
Insertion and Removal are both O(log N), reshuffling is O(N log N). Its main use is for games, think a deck of cards or a Bingo-tumbler. It isn't really a true Heap in that there's no guarantee that elements will be less than or greater than their children. But insertion and removal are both done Heap-style, just at random. (Also, unlike a regular Heap, the items do not need to be comparable to eachother.)
Is there a standard name for this sort of thing? Or maybe a better way of achieving the same results? I'm calling it a "GrabBag" for now, since that seems to describe it pretty well, but I was just wondering if there was a more widely-recognized name for it.
I looked around for possible standard names for this, but couldn't find anything. All I could find was either Randomized Meldable Heaps, which are a different thing, or people complaining about random heap corruption, which isn't even related.
O(1)
insert ,O(1)
extraction and no need for reshuffle (I don't think the reshuffle as you defined it does anything useful) and the behaviour would be easier to understand. There would be equal probability for any element to be returned next, while the probabilities are probably skewed in some non-obvious way in the "grab-bag". – Jan Hudec Jul 31 '13 at 13:34