S. Chaudhuri

G. S. Brodal, S. Chaudhuri, and J. Radhakrishnan. The Randomized Complexity of Maintaining the Minimum. Nordic Journal of Computing, 3(4):337-351, Winter 1996. Abstract, References, etc.