跳转到内容

模板:堆运行时间

维基百科,自由的百科全书

下面的时间复杂度中,[1]O(f)是一个渐近的上界,而Θ(f)是一个准确的上界(见大O符号)。函数名均假设该堆为最小堆。

操作 二叉[1] 左偏 二项[1] 斐波那契[1][2] 配对[3] Brodal[4][a]
find-min Θ(1) Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1)
delete-min Θ(log n) Θ(log n) Θ(log n) O(log n)[b] O(log n)[b] O(log n)
insert O(log n) Θ(log n) Θ(1)[b] Θ(1) Θ(1) Θ(1)
decrease-key Θ(log n) Θ(n) Θ(log n) Θ(1)[b] o(log n)[b][c] Θ(1)
merge Θ(n) Θ(log n) O(log n)[d] Θ(1) Θ(1) Θ(1)
  1. ^ Brodal和Okasaki后来描述了一个可持久化的变种,拥有同样的运行上界,但不支持decrease-key。 带有n个元素的堆可以在O(n)时间内从下至上构建。[5]
  2. ^ 2.0 2.1 2.2 2.3 2.4 均摊时间。
  3. ^ 下界为[6]上界为[7]
  4. ^ n是较大堆的大小。
  1. ^ 1.0 1.1 1.2 1.3 Cormen, Thomas H. 英语Thomas H. Cormen; Leiserson, Charles E. 英语Charles E. Leiserson; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8. 
  2. ^ Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms (PDF). Journal of the Association for Computing Machinery. July 1987, 34 (3): 596–615. doi:10.1145/28869.28874. 
  3. ^ Iacono, John, Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science 1851, Springer-Verlag: 63–77, 2000, ISBN 3-540-67690-2, arXiv:1110.4428可免费查阅, doi:10.1007/3-540-44985-X_5 
  4. ^ Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996 
  5. ^ Goodrich, Michael T.; Tamassia, Roberto. 7.3.6. Bottom-Up Heap Construction. Data Structures and Algorithms in Java 3rd. 2004: 338–341. ISBN 0-471-46983-1. 
  6. ^ Fredman, Michael Lawrence. On the Efficiency of Pairing Heaps and Related Data Structures (PDF). Journal of the Association for Computing Machinery. July 1999, 46 (4): 473–501. doi:10.1145/320211.320214. 
  7. ^ Pettie, Seth. Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183. 2005. CiteSeerX 10.1.1.549.471可免费查阅. ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.75.