Predefinição:Heap complexidade

Nas seguintes complexidades de tempo^[1] O(f) é um limite assintótico superior e Θ(f) é um limite assintótico estreito (ver Notação Big O). Os nomes das funções assumem que é um min-heap.

Operação	Binária^[1]	Binomial^[1]	Fibonacci^[1]^[2]	Brodal^[3]^[a]
encontrar-min	Θ(1)	Θ(log n)	Θ(1)	Θ(1)
remover-min	Θ(log n)	Θ(log n)	O(log n)^[b]	O(log n)
inserção	O(log n)	Θ(1)^[b]	Θ(1)	Θ(1)
diminuir-chave	Θ(log n)	Θ(log n)	Θ(1)^[b]	Θ(1)
merge	Θ(n)	O(log n)^[c]	Θ(1)	Θ(1)

↑ Brodal e Okasaki descrevem mais tarde uma variante persistente com os mesmos limites, exceto para o diminuir-chave, que não é suportado. Heaps com n elementos podem ser construídas de baixo-para-cima em O(n).^[4]
↑ ^a ^b ^c Tempo amortizado.
↑ n é o tamanho do maior heap.

↑ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill
↑ Fredman, Michael Lawrence; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms» (PDF). July 1987. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874
↑ Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
↑ Goodrich, Michael T.; Tamassia, Roberto (2004). «7.3.6. Bottom-Up Heap Construction». Data Structures and Algorithms in Java 3rd ed. [S.l.: s.n.] pp. 338–341. ISBN 0-471-46983-1

[brodal-5] Brodal e Okasaki descrevem mais tarde uma variante persistente com os mesmos limites, exceto para o diminuir-chave, que não é suportado. Heaps com n elementos podem ser construídas de baixo-para-cima em O(n).^[4]

[amortized-6] Tempo amortizado.

[merge-7] é o tamanho do maior heap.

[CLRS-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill

[Fredman_And_Tarjan-2] Fredman, Michael Lawrence; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms» (PDF). July 1987. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874

[3] Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[4] Goodrich, Michael T.; Tamassia, Roberto (2004). «7.3.6. Bottom-Up Heap Construction». Data Structures and Algorithms in Java 3rd ed. [S.l.: s.n.] pp. 338–341. ISBN 0-471-46983-1

[1]

[2]

[3]

[a]

[b]

[c]

[4]