Ho creato un contenitore che funziona come un heap binario in termini di inserimenti e fa scattare l'elemento radice. La differenza principale è che i passaggi di confronto sono tutti sostituiti da una chiamata casuale per decidere quando andare a sinistra / destra. (La struttura dati sottostante è un vettore, scritto come un array espandibile, quindi non è necessario sapere quanti elementi l'heap conterrà in anticipo.) L'idea è, è possibile inserire elementi e quando li si inserisce, si Prenderò qualsiasi elemento a caso. Puoi anche scorrere l'intera raccolta, dopo di che l'heap viene rimescolato (semplicemente facendo scoppiare e reinserire N volte).
Inserimento e rimozione sono entrambi O (log N), il rimpasto è O (N log N). Il suo uso principale è per i giochi, pensa a un mazzo di carte o a un Bingo-tumbler. Non è realmente un vero Heap in quanto non c'è alcuna garanzia che gli elementi saranno inferiori o maggiori dei loro figli. Ma l'inserimento e la rimozione sono entrambi fatti in stile Heap, solo a caso. (Inoltre, a differenza di un normale Heap, gli elementi non devono essere confrontabili tra loro).
Esiste un nome standard per questo genere di cose? O forse un modo migliore per raggiungere gli stessi risultati? Per ora lo chiamo "GrabBag", dal momento che sembra descriverlo abbastanza bene, ma mi stavo chiedendo se esistesse un nome più riconosciuto per questo.
Ho cercato possibili nomi standard per questo, ma non ho trovato nulla. Tutto quello che riuscivo a trovare erano gli heap aggregabili casuali, che sono una cosa diversa, o le persone che si lamentavano della corruzione casuale dell'heap, che non è nemmeno correlata.