Name
Abstract | ||
|---|---|---|
In this paper, we investigate the complexity of heaps. In particular, we study the construction problem and the search problem for heaps. We derive an adversary-based lower bound for the heap construction problem. It is shown that 1.5(n + 1)–log(n + 1)–2 comparisons are necessary to construct a heap of size n in the worst case. This is the first non-trivial adversary lower bound for this problem, which improves the previous best lower bound based on an information theoretical argument for the heap construction. Furthermore, we prove fairly trivial tight upper and lower bounds on the number of comparisons needed to search for a given element in a heap. An optimal 3/4n-time search algorithm is presented. Our lower bound for searching is also demonstrated by an adversary argument, which improves the information theory bound for the problem as well. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1145/139404.139483 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
construction problem,search problem,search algorithm,heap construction,information theoretical argument,size n,information theory,lower bound,heap construction problem,adversary argument,upper and lower bounds | Information theory,Discrete mathematics,Skew heap,Combinatorics,Search algorithm,Upper and lower bounds,Heap (data structure),Adversary,Search problem,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89791-466-X | 9 | 0.74 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Jingsen Chen | 2 | 66 | 9.80 |