|
[[File:Max-Heap.svg|thumb|right|Esempio di un max heap [[Albero binario|binario]] con nodi da 1 a 100]]
{{nota disambigua|la struttura dati utilizzata nell'allocazione dinamica della memoria|Gestione della memoria}}
In [[informatica]], un '''heap''' ({{lett|mucchio}}) è una [[struttura dati]] basata sugli [[Albero (informatica)|alberi]] che soddisfa la "proprietà di heap": se A è un genitore di B, allora la chiave (il valore) di A è ordinata rispetto alla chiave di B conformemente alla relazione d'ordine applicata all'intero heap. Di conseguenza, gli heap possono essere suddivisi in "'''max heap'''" e "'''min heap'''". In un max heap, le chiavi di ciascun nodo sono sempre maggiori o uguali di quelle dei figli, e la chiave dal valore massimo appartiene alla radice (detta anche nodo root). In un min heap, le chiavi di ciascun nodo sono sempre minori o uguali di quelle dei figli, e la chiave dal valore minimo appartiene alla radice.
[[File:Max-Heap.svg|thumb|right|240px|Example of a [[Complete binary tree|complete binary]] max-heap with node keys being integers from 1 to 100]]
In [[computer science]], a '''heap''' is a specialized [[Tree (data structure)|tree]]-based [[data structure]] that satisfies the ''heap property:'' If A is a parent [[Node (computer science)|node]] of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Heaps can be classified further as either a "'''max heap'''" or a "'''min heap'''". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient [[graph theory|graph]] [[algorithm]]s such as [[Dijkstra's algorithm]], and in the sorting algorithm [[heapsort]]. A common implementation of a heap is the [[binary heap]], in which the tree is a complete binary tree (see figure).
Quindi, dato un heap ''v'' ed un indice di posizione ''j'', ''v'' si dice
In a heap, the highest (or lowest) priority element is always stored at the root, hence the name '''heap'''. A heap is not a sorted structure and can be regarded as partially ordered. As visible from the Heap-diagram, there is no particular relationship among nodes on any given level, even among the siblings. When a heap is a complete binary tree, it has a smallest possible height—a heap with N nodes always has log N height. A heap is a useful data structure when you need to remove the object with the highest (or lowest) priority.
* min-heap: se <math>v[Padre(j)] < v[j], \forall j</math>
* max-heap: se <math>v[Padre(j)] > v[j], \forall j</math>
In particolare, da un punto di vista di array, descriviamo gli indici assunti da heap per i vari nodi:
* padre = <math>i/2</math>
Note that, as shown in the graphic, there is no implied ordering between siblings or cousins and no implied sequence for an [[Inorder traversal|in-order traversal]] (as there would be in, e.g., a [[binary search tree]]). The heap relation mentioned above applies only between nodes and their parents, grandparents, etc. The maximum number of children each node can have depends on the type of heap, but in many types it is at most two, which is known as a binary heap.
* nodo sinistro (left): <math>2i</math>
* nodo destro (right) <math>2i + 1</math>
In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo dell'albero e scendendo nella struttura verso le foglie, si attraversano nodi con chiave sempre maggiore dell'ultima foglia visitata. La scelta di utilizzare un tipo di heap anziché l'altro è data dal tipo di impiego che se ne vuole fare. Da notare che, come si vede nel grafo a fianco, non è implicato alcun ordine specifico tra nodi fratelli o cugini, ovvero, i nodi non sono ordinati trasversalmente (come invece accade, ad esempio, nell'[[albero binario di ricerca]]).
The heap is one maximally efficient implementation of an [[abstract data type]] called a [[priority queue]], and in fact priority queues are often referred to as "heaps", regardless of how they may be implemented. Note that despite the similarity of the name "heap" to "[[stack (abstract data type)|stack]]" and "[[queue (abstract data type)|queue]]", the latter two are abstract data types, while a heap is a specific data structure, and "priority queue" is the proper term for the abstract data type.{{Citation needed|date=November 2013}}
Gli heap sono essenziali negli [[algoritmi]] della [[teoria dei grafi]] (come l'[[algoritmo di Dijkstra]]) o negli algoritmi di ordinamento come l'[[heapsort]]. Un'implementazione molto comune di un heap è l'[[heap binario]], basato su un [[albero binario]] completo (come quello in figura). L'heap è, inoltre, una delle implementazioni più efficienti di un [[tipo di dato astratto]] chiamato [[coda di priorità]]. Essi vengono inoltre utilizzati negli algoritmi di selezione o il merge per l'elemento k-esimo, prendendo gli stream di input e convertendoli ordinatamente in stream di output.
A ''heap'' data structure should not be confused with ''the heap'' which is a common name for the pool of memory from which [[Dynamic memory allocation|dynamically allocated memory]] is allocated. The term was originally used only for the data structure.
==Operations Operazioni ==
Le operazioni comuni negli heap sono:
The common operations involving heaps are:
;''Basilari''
;Basic
* ''find-max'' oro ''find-min'': findtrova thel'elemento maximumcon itemchiave ofmaggiore adi un max-heap oro al'elemento minimumcon itemchiave ofminore adi un min-heap (a.k.a. ''[[Peek (data type operation)|peek]]'')
* ''insert'': addingaggiungi aun newnuovo key to theelemento all'heap (a.k.a., ''push''<ref>{{en}} The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappush heapq.heappush]</ref>).
* ''extract-min'' [oro ''extract-max'']: returns[[Return the(informatica)|ritorna]] nodeil ofnodo minimumdel valuevalore fromminimo adi un min heap [or(o maximummassimo valuedi from aun max heap]) afterdopo removingaverlo itrimosso fromdalla the heapstruttura (a.k.a., ''pop''<ref>{{en}} The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappop heapq.heappop]</ref>).
* ''delete-max'' oro ''delete-min'': removingrimuove thel'elemento rootradice nodedi of aun max-/min or min-heap, respectivelyrispettivamente.
*''replace'': esegue il ''pop'' sulla radice e il ''push'' di una nuova chiave.
* ''replace'': pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.<ref>{{en}} The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heapreplace heapq.heapreplace]</ref>
;Creazione
;Creation
* ''create-heap'': createcrea anun emptyheap heapvuoto.
* ''heapify'': createcrea aun heap outa ofpartire givenda un array of elements.
* ''merge'' (''union''): joiningunisce twodue heapsheap toper formformare aun valid newnuovo heap containingvalido allcontenente thetutti elementsgli ofelementi both,di preservingentrambi themantenendo originalgli heap heapsoriginali.
* ''meld'': joiningunisce twodue heapsheap toper formformare aun valid newnuovo heap containingvalido allcontenente thetutti elementsgli ofelementi bothdi entrambi, destroyingeliminando thegli originalheap heapsoriginali.
;Inspection
* ''size'': returnrestituisce theil numbernumero ofdi itemselementi indi theun heap.
* ''is-empty'': returnrestituisce <kbd>true</kbd> ifse theun heap isè emptyvuoto, <kbd>false</kbd> otherwise – an optimized form of size when total size is not neededaltrimenti.
;Altre
;Internal
* ''increase-key'' oro ''decrease-key'': updatingaumenta/decrementa ail keyvalore withindi auna max-chiave di orun max/min- heap, respectivelyrispettivamente.
*''delete'': rimuove un nodo arbitrario.
* ''delete'': delete an arbitrary node (followed by moving last node and sifting to maintain heap)
*''sift-up'': sposta un nodo in alto all'interno dell'albero; utilizzato per ripristinare la condizione di heap dopo l'inserimento. "sift" significa "setacciare".
* ''sift-up'': move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a [[sieve]].
* ''sift-down'': movesposta aun node downnodo in thebasso tree,all'interno similardell'albero; toutilizzato sift-up;per ripristinare usedla tocondizione restoredi heap conditiondopo afterla deletionrimozione oro replacementsostituzione.
== Implementazione ==
==Implementation==
Gli heap sono generalmente implementati tramite array (di dimensione fissa, o [[Array dinamico|variabile]]) e non richiede puntatori fra gli elementi. Dopo la rimozione, inserimento o sostituzione di un elemento, la proprietà di heap potrebbe essere violata, rendendo necessario il bilanciamento tramite operazioni interne.
Heaps are usually implemented in an array (fixed size or [[dynamic array]]), and do not require pointers between elements. After an element is inserted into or deleted from a heap, the heap property may be violated and the heap must be balanced by internal operations.
Gli [[Heap binario|heap binari]] possono essere rappresentati in un modo molto efficiente (dal punto di vista dello spazio) utilizzando un solo array. Il primo elemento rappresenta la radice. I due elementi seguenti contengono i figli della radice. I quattro seguenti contengono i figli dei figli, e così via. In generale, dato <math>j</math>, indice a un nodo della heap a partire da <math>j=1</math>, si definiscono padre di <math>j</math> il nodo in posizione <math>\left\lfloor \frac{j}{2}\right\rfloor</math> (dove <math>\lfloor x\rfloor</math> è la funzione [[parte intera]] di <math>x</math>), figlio sinistro di <math>j</math> il nodo in posizione <math>2j</math> e figlio destro di <math>j</math> il nodo in posizione <math>2j+1</math>.
Full and almost full [[binary heap]]s may be represented in a very space-efficient way (as an [[implicit data structure]]) using an [[array data structure|array]] alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position ''n'' would be at positions '''2n''' and '''2n + 1''' in a one-based array, or '''2n + 1''' and '''2n + 2''' in a zero-based array. This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by shift-up or shift-down operations (swapping elements which are out of order). As we can build a heap from an array without requiring extra memory (for the nodes, for example), [[heapsort]] can be used to sort an array in-place.
== Analisi asintotica ==
Different types of heaps implement the operations in different ways, but notably, insertion is often done by adding the new element at the end of the heap in the first available free space. This will generally violate the heap property, and so the elements are then shifted up until the heap property has been reestablished. Similarly, deleting the root is done by removing the root and then putting the last element in the root and shifting down to rebalance. Thus replacing is done by deleting the root and putting the ''new'' element in the root and shifting down, avoiding a shifting up step compared to pop (shift down of last element) followed by push (shift up of new element).
Nelle seguenti [[Teoria della complessità computazionale|complessità temporali]]<ref name="CLRS">{{Cita libro|cognome1= Cormen
|nome1= Thomas H.
Construction of a binary (or ''d''-ary) heap out of a given array of elements may be performed in linear time using the classic [[Heapsort#Variations|Floyd algorithm]], with the worst-case number of comparisons equal to 2''N'' − 2''s''<sub>2</sub>(''N'') − ''e''<sub>2</sub>(''N'') (for a binary heap), where ''s''<sub>2</sub>(''N'') is the sum of all digits of the binary representation of ''N'' and ''e''<sub>2</sub>(''N'') is the exponent of 2 in the prime factorization of ''N''.<ref>{{citation
|wkautore1=Thomas H. Cormen
| last1 = Suchenek | first1 = Marek A.
|cognome2= Leiserson
| title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
|nome2= Charles E.
| doi = 10.3233/FI-2012-751
|wkautore2=Charles E. Leiserson
| pages = 75–92
|cognome3= Rivest
| publisher = IOS Press
|nome3= Ronald L.
| journal = Fundamenta Informaticae
|wkautore3=Ronald Rivest
| volume = 120
|titolo= Introduction to Algorithms
| issue = 1
| year anno= 20121990
|edizione= 1ª ed.
| language = en
|editore= MIT Press and McGraw-Hill
| url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}.</ref> This is faster than a sequence of consecutive insertions into an originally empty heap, which is log-linear (or [[linearithmic]]).{{efn|Each insertion takes O(log(''k'')) in the existing size of the heap, thus <math>\sum_{k=1}^n O(\log k)</math>. Since <math>\log n/2 = (\log n) - 1</math>, a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume <math>k = n</math>; formally the time is <math>n O(\log n) - O(n) = O(n \log n)</math>. This can also be readily seen from [[Stirling's approximation]].}}
| isbn = 0-262-03141-8
|lingua= en
==Variants==
}}</ref> ''O''(''f'') è l'upper-bound asintotico, mentre ''Θ''(''f'') è l'esatto ordine di grandezza. La struttura si assume essere di tipo "min heap".
{{div col||10em}}
* [[2–3 heap]]
* [[B-heap]]
* [[Beap]]
* [[Binary heap]]
* [[Binomial heap]]
* [[Brodal queue]]
* [[D-ary heap|''d''-ary heap]]
* [[Fibonacci heap]]
* [[Leftist tree|Leftist heap]]
* [[Pairing heap]]
* [[Skew heap]]
* [[Soft heap]]
* [[Weak heap]]
* [[Leaf heap]]
* [[Radix heap]]
* [[Randomized meldable heap]]
* [[Ternary heap]]
* [[Treap]]
{{div col end}}
==Comparison of theoretic bounds for variants==
In the following [[Computational complexity theory|time complexities]]<ref name="CLRS">{{cite book
| last1 = Cormen
| first1 = Thomas H.
| author1-link=Thomas H. Cormen
| last2= Leiserson
| first2= Charles E.
| author2-link=Charles E. Leiserson
| last3= Rivest
| first3= Ronald L.
| author3-link=Ron Rivest
| last4= {{ subst:#ifexpr: 1>1 | Stein }}
| first4= {{subst: #ifexpr: 1>1 | Clifford }}
| author4-link= {{ #ifexpr: 1>1 | Clifford Stein }}
| title = {{subst: #ifeq: {{{notitlelink}}}| 1 | Introduction to Algorithms | [[Introduction to Algorithms]] }}
| origyear = {{subst: #ifexpr: 1>1 | 1990 }}
| year = {{ #switch: 1 | 1=1990 | 2=2001 | 3=2009}}
| edition = {{subst: #switch: 1 | 1=1st | 2=2nd | 3=3rd}}
| publisher = MIT Press and McGraw-Hill
| isbn = {{ subst:#switch: 1 | 1=0-262-03141-8 | 2=0-262-03293-7 | 3=0-262-03384-4}}
| language = en
| pages =
| chapter =
}}</ref> ''O''(''f'') is an asymptotic upper bound and ''Θ''(''f'') is an asymptotically tight bound (see [[Big O notation]]). Function names assume a min-heap.
{| class="wikitable"
|-
! Operazione
! Operation
! [[BinaryHeap heapbinario|BinaryBinario]]<ref name="CLRS"/>
! [[BinomialHeap heapbinomiale|BinomialBinomiale]]<ref name="CLRS"/>
! [[FibonacciHeap heapdi Fibonacci|Fibonacci]]<ref name="CLRS"/>
! [[Pairing heap|Pairing]]<ref name="Iacono">{{citationCita pubblicazione|cognome= Iacono |nome= John
|contributo= Improved upper bounds for pairing heaps
| last = Iacono | first = John
| contribution = Improved upper bounds for pairing heaps
| doi = 10.1007/3-540-44985-X_5
| pages pp= 63–7763-77
| publisher editore= Springer-Verlag
| series serie= Lecture Notes in Computer Science
| title titolo= Proc. 7th Scandinavian Workshop on Algorithm Theory
| volume lingua= 1851en
|volume= 1851
| year = 2000}}</ref>
|anno= 2000}}</ref>
! [[Brodal queue|Brodal]]<ref>{{citation | last=Brodal | first=Gerth S. | url=http://www.cs.au.dk/~gerth/papers/soda96.pdf | contribution=Worst-Case Efficient Priority Queues | title=Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms |pages=52–58 | year=1996}}</ref>{{efn|name=brodal|Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported.
Heaps with ''n'' elements can be constructed bottom-up in ''O''(''n'').<ref>{{cite book|title=Data Structures and Algorithms in Java|first1=Michael T.|last1=Goodrich|authorlink1=Michael T. Goodrich|first2=Roberto|last2=Tamassia|authorlink2=Roberto Tamassia|edition=3rd|year=2004|chapter=7.3.6. Bottom-Up Heap Construction|pages=338–341}}</ref>}}
! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal
| last1 = Haeupler | first1 = Bernhard
| last2 = Sen | first2 = Siddhartha
| last3 = Tarjan | first3 = Robert E.
| title = Rank-pairing heaps
| journal = SIAM J. Computing
| pages = 1463–1485
| year = 2009
| url = http://www.cs.princeton.edu/~sssix/papers/rp-heaps-journal.pdf}}</ref>
! [[Fibonacci heap|Strict Fibonacci]]<ref>{{cite doi|10.1145/2213977.2214082}}</ref>
|-
| ricerca minimo
| find-min
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
| rimozione minimo
| delete-min
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized|AmortizedAnalisi timeammortizzata.}}
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
|-
| inserimento
| insert
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
| decremento della chiave
| decrease-key
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|BoundedCon bylower-bound <math>\Omega(\log\log n),</math> e upper-bound <math>O(2^{2\sqrt{\log\log n}})</math><ref name="Fredman And Tarjan">{{citeCita journalpubblicazione|first1nome1=Michael Lawrence|last1cognome1=Fredman|authorlink1wkautore1=Michael Fredman|first2nome2=Robert E.|last2cognome2=Tarjan|authorlink2wkautore2=Robert Tarjan |titletitolo=Fibonacci heaps and their uses in improved network optimization algorithms| url = httphttps://www.cl.cam.ac.uk/~sos22/supervise/dsaa/fib_heaps.pdf |lingua= formaten |formato= PDF |journalrivista=[[Journal of the Association for Computing Machinery]]|volume=34|yearanno=1987|pagespp=596–-615|refcid=harv|doi=10.1145/28869.28874|issuenumero=3}}</ref><ref>{{citeCita journalpubblicazione|lastcognome=Pettie|firstnome=Seth|titletitolo=Towards a Final Analysis of Pairing Heaps|journalrivista=Max Planck Institut für Informatik|yearanno=2005|lingua=en|url=httphttps://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|-
| mergeunione
|style="background:#ffdddd"| ''Θ''(''m'' log ''n''){{efn|name=merge2|''n'' isè thela sizedimensione ofdell'heap themaggiore larger heap ande ''m'' isè thela sizedimensione ofdell'heap the smaller heapminore.}}
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' isè thela sizedimensione ofdell'heap the larger heapmaggiore.}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|}
{{Gruppo di note}}
<references group="lower-alpha/>
==Applications Applicazioni ==
L'heap ha diverse applicazioni:
The heap data structure has many applications.
*Algoritmi di ordinamento: l'[[heapsort]] è uno dei migliori metodi di ordinamento, essendo ''in-place'' e senza upper-bound quadratico.
*Algoritmi di selezione: un heap permette di accedere all'elemento con chiave minima o massima in tempo costante, e le altre selezioni (come la media o il k-esimo elemento) possono essere svolte in tempo sub-lineare.<ref>
{{Cita pubblicazione
|cognome= Frederickson
|nome= Greg N.
|contributo= An Optimal Algorithm for Selection in a Min-Heap
|doi= 10.1006/inco.1993.1030
|pp= 197-214
|lingua= en
|editore= Academic Press
|titolo= Information and Computation
|volume= 104
|numero= 2
|anno= 1993
|url= http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf
|accesso= 6 novembre 2015
|urlarchivio= https://web.archive.org/web/20121203045606/http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf
|dataarchivio= 3 dicembre 2012
|urlmorto= sì
}}
</ref>
*Algoritmi sui grafi: l'heap trova applicazione in svariati metodi, come l'[[algoritmo di Prim]] per la ricerca dell'[[albero ricoprente minimo]] o l'[[algoritmo di Dijkstra]] per la ricerca del [[cammino minimo]].
*Code di priorità: uno dei modi di implementare le [[Coda di priorità|code di priorità]] è tramite heap.
*[[Statistica d'ordine]]: l'heap può essere usato per trovare efficientemente il k-esimo elemento minore (o maggiore) in un array.
== Implementazioni ==
* [[Heapsort]]: One of the best sorting methods being in-place and with no quadratic worst-case scenarios.
*La libreria standard [[C++]] fornisce gli algoritmi <kbd>make_heap</kbd>, <kbd>push_heap</kbd> e <kbd>pop_heap</kbd> per gli heaps (di solito implementati come heap binari), che operano su [[Iteratore|iteratori]] ad accesso casuale.
* [[Selection algorithm]]s: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.<ref>{{citation
*Fra le librerie C++ [[Boost (C++)|Boost]] c'è una libreria di heap. Al contrario della STL, quest'ultima supporta anche le operazioni di incremento e decremento, e supporta tipi addizionali di heap: nello specifico, supporta gli heap ''d''-ari, binomiali, di Fibonacci, pairing e skew.
| last = Frederickson | first = Greg N.
*Il linguaggio [[Java (linguaggio di programmazione)|Java]] (dalla versione 1.5) fornisce gli heap binari con la classe [https://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html <kbd>java.util.PriorityQueue<E></kbd>] della [[Java Collections Framework]]. Non supporta le operazioni di incremento e decremento.
| contribution = An Optimal Algorithm for Selection in a Min-Heap
*[[Python]] ha un modulo [https://docs.python.org/library/heapq.html <kbd>heapq</kbd>] che implementa una coda di priorità tramite un albero binario.
| doi = 10.1006/inco.1993.1030
*[[PHP]] supporta sia max-heap (<kbd>SplMaxHeap</kbd>) che min-heap (<kbd>SplMinHeap</kbd>) dalla versione 5.3 della Standard PHP Library.
| pages = 197–214
*[[Perl]] supporta le implementazioni di heap binari, binomiali e di Fibonacci nella distribuzione [https://metacpan.org/module/Heap <kbd>Heap</kbd>] disponibile su [[CPAN]].
| publisher = Academic Press
*La libreria [[Core Foundation]] Apple contiene la struttura [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html <kbd>CFBinaryHeap</kbd>].
| title = Information and Computation
| volume = 104
| issue = 2
| year = 1993
| url = http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf}}</ref>
* [[List of algorithms#Graph algorithms|Graph algorithms]]: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are [[Prim's algorithm|Prim's minimal-spanning-tree algorithm]] and [[Dijkstra's algorithm|Dijkstra's shortest-path algorithm]].
== Note ==
*[[Priority Queue]]: A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.
<references/>
*[[Order statistics]]: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.
==Implementations==
* The [[C++]] [[Standard Library]] provides the <tt>make_heap</tt>, <tt>push_heap</tt> and <tt>pop_heap</tt> algorithms for heaps (usually implemented as binary heaps), which operate on arbitrary random access [[iterator]]s. It treats the iterators as a reference to an array, and uses the array-to-heap conversion. It also provides the container adaptor <tt>priority_queue</tt>, which wraps these facilities in a container-like class. However, there is no standard support for the decrease/increase-key operation.
* The [[Boost (C++ libraries)|Boost C++ libraries]] include a heaps library. Unlike the STL it supports decrease and increase operations, and supports additional types of heap: specifically, it supports ''d''-ary, binomial, Fibonacci, pairing and skew heaps.
* The [[Java (programming language)|Java]] 2 platform (since version 1.5) provides the binary heap implementation with class [http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html <tt>java.util.PriorityQueue<E></tt>] in [[Java Collections Framework]]. However, there is no support for the decrease/increase-key operation.
* [[Python (programming language)|Python]] has a [https://docs.python.org/library/heapq.html <tt>heapq</tt>] module that implements a priority queue using a binary heap.
* [[PHP]] has both max-heap (<tt>SplMaxHeap</tt>) and min-heap (<tt>SplMinHeap</tt>) as of version 5.3 in the Standard PHP Library.
* [[Perl]] has implementations of binary, binomial, and Fibonacci heaps in the [https://metacpan.org/module/Heap <tt>Heap</tt>] distribution available on [[CPAN]].
* The [[Go (programming language)|Go]] language contains a [http://golang.org/pkg/container/heap/ <tt>heap</tt>] package with heap algorithms that operate on an arbitrary type that satisfy a given interface.
* Apple's [[Core Foundation]] library contains a [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html <tt>CFBinaryHeap</tt>] structure.
* [[Pharo]] has an implementation in the Collections-Sequenceable package along with a set of test cases. A heap is used in the implementation of the timer event loop.
* The [[Rust (programming language)|Rust]] programming language has a binary max-heap implementation, [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html <tt>BinaryHeap</tt>], in the <tt>collections</tt> module of its standard library.
== Voci correlate ==
* [[Treap]]
== NoteAltri progetti ==
{{interprogetto|preposizione=sull'|wikt=heap}}
<references/>
<!--== AltriCollegamenti progettiesterni ==
* {{Collegamenti esterni}}
{{interprogetto}}
* {{FOLDOC||heap}}
{{strutture dati}}
== Collegamenti esterni ==
{{portale|informatica|matematica}}
*{{en}} [http://mathworld.wolfram.com/Heap.html Heap] su Wolfram MathWorld
[[Categoria:Heap| ]]--
| 