On lower bounds for constructing heaps

Abstract

A heap is an elegant and important data structure for representing a priority queue, and it has been widely studied. Based on two analogous conjectures, we prove lower bounds on the worst-case time-complexity of constructing heaps, in the comparison tree and the linear decision tree models. The conjectures roughly state the following: For any positive integer k, given a set of 2 ^k –2 real numbers, constructing two disjoint heaps of 2^k-1–1 real numbers each can be done most efficiently by splitting the given set into two subsets of equal size, and then independently constructing a heap on each subset. Based on these conjectures, we show that any comparison tree (respectively, linear decision tree) for constructing a heap must perform at least l.4922n –o(n) (respectively, 1.4681 n–o(n)) comparisons in the worst case. Our lower bound for comparison trees is slightly inferior to the previously known lower bound of 1.5n –0(lg n) comparisons; but our proof is based on the structure of comparison trees, and is much easier to understand. Our lower bound for linear decision trees is significantly better than the previously known lower bound of 1.3644n –o(n).

Keywords:

• Heaps
• comparison tree model
• linear decision tree model
• timecomplexity
• wors-case performance
• lower bound