Struttura dei dati per l'ordinamento in base a più attributi

Penso che potresti pensarci troppo o cercare di complicarlo più del necessario.

Quando una coppia deve essere modificata, rimuovila da entrambi gli heap, modificala, quindi aggiungila a entrambi gli heap.

Un piccolo problema che potresti incontrare è che una volta che hai trovato in un heap una coppia che vuoi modificare, come trovare quella coppia nell'altro heap. Se le coppie sono uniche, questo non è un problema. Se le coppie sono non univoche, potrebbe essere necessario aggiungere un campo per identificarle in modo univoco. A meno che la lingua che stai usando fornisce già un qualche tipo di identità. (Ad esempio, in Java, è possibile confrontare per riferimento.)

Il tuo problema può essere suddiviso in due parti:

• un algoritmo di ordinamento che prende un value da un dato elemento
• un metodo per scegliere quale value estrarre, dato un nome di funzione

Quindi qualcosa come (pseudocodice simile a Python):

data = new MyDataStructure()
#Insert some values into it..
#...

def extract_feature(myObject, feature_name):
   return myObject.getFeature(feature_name)


print sorted(data, (key=lambda x: extract_feature(x))

Ri: il tuo commento Stai parlando di strutture dati, ma quello che sei veramente dopo ... è un algoritmo di ordinamento in grado di prendere un tipo di oggetto e modificare al volo la chiamata di a.compareTo(b) . In altre parole, qualsiasi datastructure farà. Il tuo algoritmo di ordinamento ha solo bisogno di sapere come calcolare la chiave con cui verrà eseguito l'ordinamento.

Esempio: link

Quello che stai cercando veramente è la somma del 50% più alto degli elementi.

Dato un insieme di coppie n , ci sono 2 elementi n . Dividiamo questi elementi in due sequenze (non insiemi, elementi possono verificarsi più volte), s e t contenenti ciascuno elementi n . Scambiamo elementi finché è vero che per ogni elemento e in s e f in t , che e < = f .

Ora riassumi semplicemente gli elementi in t , dandoci il risultato. Questo è molto simile all'ordinamento degli elementi in ogni coppia, scartando la metà degli elementi più piccoli e sommando il resto.

Il modo più semplice per ottenere questi risultati è il seguente algoritmo:

1. Dividi ogni coppia in n in due numeri e inseriscili nella lista t .
2. Ordina l'elenco t in ordine decrescente.
3. Somma i primi c / 2 elementi in cui c è il numero di elementi nell'elenco (garantito pari).