𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Best Case of Heapsort

✍ Scribed by B. Bollobás; T.I. Fenner; A.M. Frieze

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
169 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Although discovered some 30 years ago, the Heapsort algorithm is still not completely understood. Here we investigate the best case of Heapsort. Contrary to Ž . claims made by some authors that its time complexity is O n , i.e., linear in the Ž . number of items, we prove that it is actually O n log n and is, in fact, approximately half that of the worst case. Our proof contains a construction for an asymptotically best-case heap. In addition, the proof and construction provide the worst-case time complexity and an asymptotically worst-case example for Bottom-up versions of Heapsort.

📜 SIMILAR VOLUMES

The Analysis of Heapsort
The Analysis of Heapsort
✍ R. Schaffer; R. Sedgewick 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 990 KB
Best medical practice: The case of Japan
Best medical practice: The case of Japan
✍ Naoki Ikegami 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 952 KB

'Best medical practice' can be given three different definitions. Definition A, by the medical profession, emphasizes the maintenance of technical standards in diagnosis and treatment. Definition B, by the essentially healthy general population, emphasizes preventive measures and the reassurance of

On the best arrangement of city streets
On the best arrangement of city streets
✍ Lewis M. Haupt 📂 Article 📅 1877 🏛 Elsevier Science 🌐 English ⚖ 272 KB

It may be safely assumed that facility of communication is one of the most potent elements of human progression and development, hence any obstacle to mobility, however small, becomes a bar to progress, and should, if possible, be removed. It becomes immediately evident therefore, that the rectangu