Perché la maggior parte delle lingue fornisce un min-heap invece di un'implementazione massima dell'heap?

Question

Perché la maggior parte delle lingue fornisce un min-heap invece di un'implementazione massima dell'heap?

#1 da (8 voti)
#2 da (5 voti)
#3 da (3 voti)
#4 da (1 voti)

18

Ho appena notato qualcosa e mi chiedo se c'è qualche ragione per questo. Tranne che per C ++ (std :: priority_queue è un heap massimo), non conosco nessun altro linguaggio che offra un heap massimo.

Python's heapq module implements a binary min-heap on top of a list.

Java's library contains a PriorityQueue class, which implements a min-priority-queue.

Go's library contains a container/heap module, which implements a min-heap on top of any compatible data structure.

Apple's Core Foundation framework contains a CFBinaryHeap structure, which implements a min-heap.

Trovo che un max-heap sia più intuitivo di un min-heap e credo tecnicamente che la differenza di implementazione sia solo una questione di modifica di un operatore di confronto. C'è una vera ragione? La maggior parte delle applicazioni richiede un min invece di un heap massimo? Grazie in anticipo

design algorithms

posta Bernardo Pires 17.05.2011 - 12:12

fonte

4 risposte

5

È solo una questione di gusti. Non penso ci sarà alcuna ragione specifica. È come se alcune persone amassero esprimere problemi di ottimizzazione riducendo al minimo i costi, mentre altri come dire massimizzano il profitto.

risposta data 17.05.2011 - 13:39

fonte

3

La maggior parte delle lingue che conosco consentono di passare un parametro per decidere se deve essere un heap minimo o massimo. Quindi il valore predefinito è in qualche modo arbitrario. Suppongo che per la maggior parte delle lingue sia una questione di coerenza definire cosa sia l'operatore predefinito. Per C ++ in the stl il valore predefinito è std::less che porta a un min-heap.

La coerenza dell'uso di std::less per default ovunque significa che devi solo implementare questo confronto quando usi un qualsiasi tipo di struttura dati e non devi decidere su quale struttura dati utilizzerai in seguito quando progetti le tue lezioni Direi che è lo stesso per le altre lingue, con l'unica differenza che un confronto più grande è lo standard.

risposta data 17.05.2011 - 12:55

fonte

1

Fondamentalmente, il valore dell'indice è un numero arbitrario. Se ritieni che il numero rappresenti una priorità e numeri più grandi abbiano priorità più alte, allora un max-heap ha senso. Ma se i numeri rappresentano, ad esempio, numeri di panetteria concettuali ("Prendi un numero"), il min-heap ha più senso.

Puoi sempre convertire da uno all'altro prendendo il complemento 1 dell'indice.

risposta data 17.05.2011 - 14:04

fonte

Leggi altre domande sui tag design algorithms

Come faccio a testare un lettore di file? Perché usare le classi quando si programma un tkinter gui in python

score 8 · Accepted Answer

Come altri hanno osservato, se l'heap accetta un comparatore, non è troppo difficile ottenere un comportamento o l'altro. Una rapida lettura del codice di Google, tuttavia, suggerisce che il min-heap è di gran lunga più diffuso nel codice reale, a causa di due applicazioni che si verificano più e più volte.

Dijkstra / A * / molti altri algoritmi di percorso più breve (perché i percorsi parziali si allungano).
Simulazione degli eventi (perché il tempo va avanti).

Inoltre, direi che poiché l'ordinamento predefinito restituisce elementi da piccoli a grandi, anche l'heap predefinito.