Thursday, June 23, 2011

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 19

The authors discuss binomial heaps in this chapter. The authors defined binomial trees and then binomial heaps and prove some of their properties. The authors then define CREATE, MINIMUM, LINK, UNION, MERGE, INSERT, EXTRACT-MIN, DECREASE-KEY and DELETE operations on the binomial heaps. Except CREATE, which takes $ \Theta(1) $ time, all the other operations take running time which is $ O(\lg n) $.

No comments:

Post a Comment