Heap (struttura dati): differenze tra le versioni

Versione delle 18:53, 16 apr 2019

Versione delle 02:12, 2 mag 2019

Riga 96:

|style="background:#ffffdd"| ''Θ''(log ''n'')

|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}

|style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|Con lower-bound <math>\Omega(\log\log n)</math> e upper-bound <math>O(2^{2\sqrt{\log\log n}})</math><ref name="Fredman And Tarjan">{{Cita pubblicazione|nome1=Michael Lawrence|cognome1=Fredman|wkautore1=Michael Fredman|nome2=Robert E.|cognome2=Tarjan|wkautore2=Robert Tarjan |titolo=Fibonacci heaps and their uses in improved network optimization algorithms|url= httphttps://www.cl.cam.ac.uk/~sos22/supervise/dsaa/fib_heaps.pdf |lingua= en |formato= PDF |rivista=[[Journal of the Association for Computing Machinery]]|volume=34|anno=1987|pp=596–615|cid=harv|doi=10.1145/28869.28874|numero=3}}</ref><ref>{{Cita pubblicazione|cognome=Pettie|nome=Seth|titolo=Towards a Final Analysis of Pairing Heaps|rivista=Max Planck Institut f&uuml;r Informatik|anno=2005|lingua=en|url=httphttps://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}

|-

| unione

Riga 136:

*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.

*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.

*Il linguaggio [[Java (linguaggio di programmazione)|Java]] (dalla versione 1.5) fornisce gli heap binari con la classe [httphttps://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html <kbd>java.util.PriorityQueue&lt;E&gt;</kbd>] della [[Java Collections Framework]]. Non supporta le operazioni di incremento e decremento.

*[[Python]] ha un modulo [https://docs.python.org/library/heapq.html <kbd>heapq</kbd>] che implementa una coda di priorità tramite un albero binario.

*[[PHP]] supporta sia max-heap (<kbd>SplMaxHeap</kbd>) che min-heap (<kbd>SplMinHeap</kbd>) dalla versione 5.3 della Standard PHP Library.