Esiste un nome per un heap randomizzato?

3

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.

    
posta Darrel Hoffman 31.07.2013 - 01:41
fonte

1 risposta

1

Questo bisogno si presenta molto nella programmazione del gioco quando si vuole garantire una certa distribuzione di probabilità nel tempo. Per esempio, se l'orco dovesse colpire il 30% delle volte, crei una Borsa con 30 colpi e 70 mancati, in ordine casuale, quindi fai un pop dalla fine dell'array ogni volta che ne hai bisogno.

Di solito è implementato come un array, quindi la creazione è O(n) (cioè l'inserimento è O(1) ) e la rimozione è O(1) . (Non è necessario alcun rimpasto, è sufficiente ricrearlo quando ne hai bisogno uno nuovo. Il tuo rimpasto può essere implementato spingendo ogni oggetto estratto in un nuovo heap mentre lo fai apparire, quindi sono simili.) La soluzione array sarà un performer superiore sia in fase di recupero, a meno che non sia possibile inserire in batch.

Inoltre, sono preoccupato per l'effettiva casualità del tuo algoritmo. A meno che non si affondino casualmente nodi non foglia durante l'inserimento, i nodi precedenti tendono a essere in cima all'albero. Mi manca qualcosa?

    
risposta data 31.07.2013 - 15:13
fonte

Leggi altre domande sui tag