Sto lavorando contro un'API in cui posso aggiungere e aggiornare elementi in un elenco ordinato da un campo di priorità che posso impostare (che non deve essere contiguo ma deve essere un numero intero positivo).
L'aggiornamento di un membro della lista è un'operazione costosa, quindi voglio ridurre al minimo il numero di aggiornamenti.
Quello che voglio è un algoritmo che ridurrà al minimo il numero di aggiornamenti richiesti quando l'elenco viene riordinato.
vale a dire. Lo scenario peggiore per questo è usare priorità contigue a partire da 1. ad es.
Priority | item
----------------
1 A
2 B
3 C
4 D
5 E
In questo caso per spostare l'elemento E in cima all'elenco, ogni singolo elemento dovrebbe avere la sua priorità aggiornata.
La soluzione ingenua che ho è di implementare grandi numeri per le priorità e inserire priorità che sono a metà dell'intervallo tra due elementi quando un articolo deve essere posizionato lì.
per es.
Priority | item
----------------
1000000 A
2000000 B
3000000 C
4000000 D
5000000 E
In questo caso per spostare E verso l'alto è richiesto solo un aggiornamento (e posso impostare la sua priorità su 500000)
Il problema è che agirà come una ricerca binaria e anche nel caso in cui si utilizzino numeri iniziali dell'ordine di 10 ^ 9 saranno necessarie solo 30 operazioni finché le priorità non diventeranno contigue.
Esiste un algoritmo migliore di questo? C'è uno esistente che posso usare (ma non ho trovato tramite google), o qualcuno può suggerire un miglioramento a questo?