Differenza tra un heap e una coda di priorità

Question

Differenza tra un heap e una coda di priorità

#1 da (18 voti)
#2 da (3 voti)
#3 da (2 voti)

27

Ho sempre pensato che gli heap e le code di priorità fossero sinonimi: una struttura di dati astratta che supporta le operazioni insert , findMin e deleteMin .

Alcune pubblicazioni sembrano essere d'accordo con me - Purely Functional Data Structures di Chris Okasaki (capitolo 3), per esempio.

D'altra parte, la pagina heap di Wikipedia la definisce come una struttura di dati basata sugli alberi e afferma quegli heap sono un'implementazione concreta delle code di priorità.

Ho difficoltà a conciliare ciò con il fatto che posso pensare a più di una implementazione dell'heap: heap di sinistra, heap binomiali, heap di splay ...

Il semplice fatto che un heap possa essere implementato con strutture di dati differenti non significa, per definizione, che si tratti di una struttura di dati astratta? E se questo è il caso, c'è una differenza reale con le code di priorità?

data-structures

posta Nicolas Rinaudo 31.08.2014 - 17:44

fonte

3 risposte

Leggi altre domande sui tag data-structures

Qual è il modo migliore per costruire una fabbrica usando NInject? Ci sono ragioni diverse dal budget per assumere programmatori "entry-level"? [chiuso]

score 18 · Answer 1

Una coda di priorità può avere qualsiasi implementazione, come una matrice che si cerca linearmente quando si apre. Tutto ciò significa che quando apri ottieni il valore con il minimo o il massimo a seconda.

Un heap classico come di solito si parla di solito è un heap minimo. Un'implementazione con una buona complessità temporale ( O(log n) su push e pop) e nessun sovraccarico di memoria.

score 3 · Answer 2

Questo sito fornisce una spiegazione molto chiara. link

In breve, una coda di priorità può essere implementata utilizzando molte delle strutture di dati che abbiamo già studiato (un array, un elenco collegato o un albero di ricerca binario). Tuttavia, tali strutture di dati non forniscono le operazioni più efficienti. Per rendere tutte le operazioni molto efficienti, utilizzeremo una nuova struttura dati chiamata heap.

score 2 · Answer 3

Penso che quello che hai scritto sul concreto rispetto all'astratto sia corretto. Dove si dice che gli heap di splay, gli heap binomiali sono differenti implementazioni di heap, penso che sia più corretto dire che sono diversi tipi di heap. Heap Penso a una categoria di implementazione che generalmente garantisce non solo la stessa interfaccia, ma anche gli stessi tempi di accesso.

Lo si vede con mappe associative, tabelle di hash e alberi di ricerca binaria. Le tabelle Bsts e hash sono entrambe strutture di dati concreti che forniscono l'interfaccia astratta della mappa associativa. Gli alberi neri rossi e gli alberi AV sono entrambi bs bilanciati, con le stesse grandi garanzie O e la stessa interfaccia aggiuntiva (nell'ordine trasversale). Sono diversi tipi di alberi direi più delle diverse implementazioni di alberi. Sono implementazioni diverse ma strettamente correlate di mappe associative.