Wikipedia dice:Come trovo la mediana dei numeri in tempo lineare usando gli heap?
algoritmi di selezione: trovare la min, max, sia il minimo e massimo, mediana, o anche l'elemento più grande k-esimo può essere fatto in tempo con cumuli lineari.
Tutto ciò che dice è che può essere fatto, e non come.
Puoi darmi un po 'di anticipo su come questo può essere fatto usando gli heap?
Si utilizzerà un heap min-max-mediano per trovare il minimo, il massimo e la mediana in tempo costante (e prendere il tempo lineare per costruire l'heap). Puoi utilizzare gli alberi delle statistiche degli ordini per trovare il k più piccolo/valore più grande. Entrambe queste strutture di dati sono descritte in this paper on min-max heaps [pdf link]. Gli heap min-max sono heap binari che si alternano tra min-heap e max-heap.
Dalla carta: Un mucchio min-max-mediana è un cumulo binaria con le seguenti proprietà:
1) La mediana di tutti gli elementi si trova alla radice
2) Il sottoalbero sinistro la radice è un HL min-max di dimensione del soffitto [((n-1)/2)] contenente elementi inferiori o uguali alla mediana. Il sottoalbero di destra è un Hr di dimensioni massime min. [((N-1)/2)] contenente solo elementi maggiori o uguali alla mediana.
Il foglio continua a spiegare come creare un simile heap.
Modifica: dopo aver letto il documento più a fondo, sembra che la costruzione degli heap min-max-mediani richieda di trovare prima la mediana (FTA: "Trova la mediana di tutti gli n elementi usando uno qualsiasi dei noti linear- algoritmi del tempo "). Detto questo, una volta costruito l'heap, è possibile mantenere la mediana semplicemente mantenendo l'equilibrio tra l'heap min-max a sinistra e l'heap max-min a destra. DeleteMedian sostituisce la radice con il min dell'heap max-min o il massimo dell'heap min-max (a seconda di quale mantiene il saldo).
Quindi, se si prevede di utilizzare un heap min-max-mediano per trovare la mediana di un set di dati fisso, si è SOL ma se lo si utilizza su un set di dati modificabile è possibile.
In realtà, entrambi gli heap possono essere min-max o max-min e l'algoritmo continuerà a funzionare con la stessa complessità generale – dhruvbird
Vedere questa pagina di wikipedia su selection algorithms. In particolare, guarda l'algoritmo BFPRT e l'algoritmo Median of Medians. BFPRT è probabilisticamente lineare ed è modellato su quicksort; La mediana delle mediane è garantita linearmente, ma ha un grande fattore costante e quindi potrebbe richiedere più tempo in pratica, a seconda della dimensione del set di dati.
Se si dispone solo di alcune centinaia di migliaia di elementi tra cui selezionare la mediana, sospetto che una semplice quicksort seguita dall'indicizzazione diretta sia più semplice.
@Dale Hagglund: "using heaps"? – Lazer
"linear" non è compatibile con "using heaps" a meno che tu non stia introducendo il costo di pre-elaborazione gratuitamente. Tuttavia, avrei dovuto chiarirlo all'inizio del mio post. –
È davvero così difficile applicare il concetto di heap a partizioni e pivot? – tloflin
Non ci sono algoritmi probabilmente meglio là fuori, ma ecco come lo farei:
avere due secchi e un valore. Il valore è la mediana, i due secchi sono "più grandi della mediana" e "più piccoli della mediana". Per ciascun elemento x nell'array, ribilanciare i bucket in modo tale che big_bucket e small_bucket non differiscano di più di 1 nella loro dimensione. Quando si spostano gli oggetti dal secchio grande al secchio piccolo, per prima cosa devono passare attraverso il valore mediano per arrivarci (ovvero, una differenza di 2 spinge con successo un elemento da un secchio all'altro - una differenza di 1 spingerà un elemento da un segmento al valore medio.) Alla fine del primo passaggio attraverso l'array, il valore dovrebbe essere la mediana.
@fbrereto: quale sarebbe la complessità temporale del tuo algoritmo? Penso che questo algoritmo NON sia lineare. – Lazer
Sarebbe un passaggio attraverso l'array originale e le operazioni di bucket sarebbero push/pop, che possono essere eseguite in tempo costante (poiché la loro dimensione è notoriamente non superiore a N/2 + 1), quindi In cima alla mia testa, sospetto che possa essere fatto in O (N). Per favore correggimi se ho perso qualcosa. – fbrereto
Hrm ... si dovrebbero mantenere ordinati i bucket, che non è un'operazione di tipo O (N) (mod un ordinamento di tipo radix). – fbrereto
Ovviamente, min e max in O (n) sono semplici e non richiedono un heap.
K'th più grande può essere fatto abbastanza semplicemente mantenendo un heap k-sized dei primi valori k finora. Il runtime dovrebbe essere O (n * logk). Potresti chiamare quel tempo lineare se k è dimensione fissa e k < < n.
Non penso però che la mediana sia possibile. La creazione di un heap di dimensioni O (n) richiede tempo O (n * logn).
Modifica: Ok, dopo aver pensato un po 'di più, IVlad ha ragione. È possibile creare un heap in O (n), per una dimensione fissa. Ma ... questo non aiuta l'OP con la sua domanda mediana. La tecnica di creazione lineare dell'heap produce solo un heap valido come output finale. L'approccio semplice di fare n inserimenti, risultante in un heap valido dopo ogni passaggio è O (n * logn).
Mi sembra che l'utilizzo di heap per trovare la mediana richiederebbe l'utilizzo di quelli che eseguono sotto-heap. Ad esempio, c'è stata una risposta pubblicata qui (che sembra essere cancellata ora) collegata a un post sul blog che suggerisce un algoritmo per questo problema. Tracciava la mediana corrente usando due heap (la metà più piccola e la metà più grande) mentre eseguiva un singolo passaggio attraverso i dati. Ciò richiederebbe l'approccio più lento e ingenuo dell'heap perché dipende dal mantenimento di heap validi che inserisce e rimuove da essi.
C'è un altro modo per trovare la mediana utilizzando la tecnica di creazione di un mucchio lineare one-shot?
"La creazione di un heap di dimensioni O (n) richiede tempo O (n * logn)" - errato, è possibile creare un heap in tempo O (N). – IVlad
@IVlad - È possibile creare un heap per dati già ordinati in tempo O (n) ed è possibile creare un heap a dimensione fissa in tempo O (n), ma non vedo nessuna di quelle precondizioni nella domanda . –
Se i dati sono già ordinati, non è necessario un heap per trovare la mediana o uno degli altri obiettivi nell'OP. – Alan
se ne sai di più sulla struttura dei dati heap, capirai facilmente che è proprio così. la struttura dell'heap può essere costruita in tempo O (n), c'è un heap minimo e un heap massimo. L'elemento min heap root ti darà l'elemento più piccolo. l'elemento root dell'heap massimo ti darà l'elemento massimo. Semplicemente costruendo l'heap trovi il minimo e il massimo. stessa idea per mediana e kth più grande, mentre costruisci il tuo heap, puoi trovare la mediana e la k più grande guardando il ramo sinistro o destro dell'albero e mantenendo una quantità costante di memoria per memorizzare il numero dell'elemento. ecc.
@ user177883: come si costruisce un heap in modo che la radice sia la mediana? – Lazer
forse wasnt intorno quando la domanda iniziale è stato chiesto, ma ora wiki ha un link alla fonte, e qui è: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf
specificamente, vai alla pagina 17, e guardare la descrizione di RSEL4. Dimostrano nel teorema 3.2 che la complessità temporale di questo algoritmo di selezione k-esima è O (k). quindi ci vorrebbe O (n) per costruire l'heap, e un extra O (k) per trovare il k-esimo oggetto più piccolo.
non è davvero così semplice come alcune delle altre risposte hanno suggerito
Conservare il primo intero nella matrice e impostare un contatore a 1. Poi scorrere i restanti interi nel vettore. Se il numero intero corrente dell'array è uguale a quello memorizzato, il contatore viene aumentato di uno, altrimenti il contatore viene diminuito di uno. Se il contatore raggiunge mai lo zero, elimina il numero intero memorizzato e sostituiscilo con il numero intero corrente nell'array. Quando finalmente si passa in rassegna tutti gli interi, si rimane con un candidato. È quindi necessario eseguire nuovamente il ciclo dell'array e contare l'occorrenza del candidato per verificare che questo sia davvero un dominatore.
static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
if(arr[i] == candidate) counter++
else
{
counter--;
if(counter == 0) { candidate = arr[i]; counter = 1; }
}
}
counter = 0;
for(int i = 0; i < n; i++)
{
if(arr[i] == candidate) counter++;
}
if(counter > n/2) return candidate;
else return -1;
}
Penso che possa essere sbagliato in merito alla mediana e al k-esimo, ma sarei molto felice di essere smentito, soprattutto per la mediana. –
Duplicato: http: // stackoverflow.it/questions/810657/quick-code-c-c-to-select-the-median-in-a-set-of-27-floating-point-values – Jacob
Non è un duplicato. (Penso, ma potrebbe essere sbagliato) non si tratta di algoritmi di selezione, ma di ottenere mediana per essere O (1) volta, dopo che gli heap sono stati creati. –