Allo scopo di implementare un algoritmo di ottimizzazione (trovando il minimo di una funzione multivariata) voglio creare una struttura dati che supporti le seguenti operazioni:
- carica dall'array
- Guarda l'elemento massimo (ma non distruggerlo)
- Guarda l'elemento prossimo al massimo
- Sbircia l'elemento minimo
- diminuisce l'elemento massimo
Una volta inizializzato, la struttura dati memorizza sempre lo stesso numero di elementi.
Attualmente sto solo usando una matrice non ordinata e cercando ogni volta l'array per trovare gli elementi max, next-to-max e min e aggiornando l'elemento max quando necessario.
Ho preso in considerazione l'utilizzo di una coda heap / priorità, ma questi non sembrano ideali, in quanto supportano l'aggiunta e la rimozione di elementi, cosa che non devo fare. Inoltre, non supportano in modo nativo "diminuisci l'elemento massimo", semplicemente "aumentano un elemento arbitrario", quindi dovrei estrarre -max e quindi aggiungerlo nuovamente.
Ho anche considerato una matrice ordinata in un buffer circolare, che sembra sarebbe meglio di un array ordinato, poiché dovrei spostarmi solo alla metà della lista.
Wikipedia parla di alcune complicate strutture di dati (heap di Fibonacci) che ricordo vagamente dai miei algoritmi del secondo anno di college, ma sembrano eccessivi (e supportano anche funzionalità che non mi servono e non supportano le funzionalità di cui ho bisogno ).
Bene, ora cerco di nuovo e trovo che la mia domanda è una specie di duplicato di link