Heap (struttura dati): differenze tra le versioni

Versione delle 00:21, 27 ott 2022

Versione attuale delle 20:58, 22 giu 2025

(9 versioni intermedie di 6 utenti non mostrate)

Riga 17:

== Operazioni ==

Le operazioni comuni negli heap sono:

;''Basilari''

;Basiche

*''find-max'' o ''find-min'': trova l'elemento con chiave maggiore di un max-heap o l'elemento con chiave minore di un min-heap.

*''insert'': aggiungi un nuovo elemento 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>).

Riga 26:

;Creazione

*''create-heap'': crea un heap vuoto.

*''heapify'': crea un heap a partire dida un array.

*''merge'' (''union''): unisce due heap per formare un nuovo heap valido contenente tutti gli elementi di entrambi mantenendo gli heap originali.

*''meld'': unisce due heap per formare un nuovo heap valido contenente tutti gli elementi di entrambi, eliminando gli heap originali.

;Inspection

*''size'': ritornarestituisce il numero di elementi di un heap.

*''is-empty'': ritornarestituisce <kbd>true</kbd> se un heap è vuoto, <kbd>false</kbd> altrimenti.

;Altre

Riga 54:

|cognome3= Rivest

|nome3= Ronald L.

|wkautore3=RonRonald Rivest

|titolo= Introduction to Algorithms

|anno= 1990

Riga 65:

{| class="wikitable"

|-

! Operazione

! Operation

! [[Heap binario|Binario]]<ref name="CLRS"/>

! [[Heap binomiale|Binomiale]]<ref name="CLRS"/>

Riga 72:

|contributo= Improved upper bounds for pairing heaps

| doi = 10.1007/3-540-44985-X_5

|pp= 63–7763-77

|editore= Springer-Verlag

|serie= Lecture Notes in Computer Science

Riga 102:

|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= https://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–615596-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=https://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}

|-

| unione

Riga 121:

|contributo= An Optimal Algorithm for Selection in a Min-Heap

|doi= 10.1006/inco.1993.1030

|pp= 197–214197-214

|lingua= en

|editore= Academic Press

Riga 159:

== Altri progetti ==

{{interprogetto|preposizione=sull'|wikt=heap}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

*{{en}} [http://mathworld.wolfram.com/Heap.html Heap] su Wolfram MathWorld

* {{FOLDOC||heap}}

{{strutture dati}}