Difference between revisions of "Talk:Binary heap"
(Created page with "This is the first time I have seen an average case analysis of the binary heap operations, and it is very helpful to know what they are since it shows that in practical real-worl...") |
(noted incorrect analysis of adding an element) |
||
| Line 1: | Line 1: | ||
This is the first time I have seen an average case analysis of the binary heap operations, and it is very helpful to know what they are since it shows that in practical real-world applications, it is probably better than many other structures mainly because of the low constants involved. Plus, the average case analysis helps analyze the average case running time of other algorithms that use the binary-heap as an auxiliary data structure. | This is the first time I have seen an average case analysis of the binary heap operations, and it is very helpful to know what they are since it shows that in practical real-world applications, it is probably better than many other structures mainly because of the low constants involved. Plus, the average case analysis helps analyze the average case running time of other algorithms that use the binary-heap as an auxiliary data structure. | ||
| + | |||
| + | |||
| + | UPDATE: The analysis of the expected number of swaps used when adding an element is incorrect. It assumes a uniform distribution of keys, but keys are certainly not uniformly distributed in a heap. In a min-heap, smaller keys are far more likely to be near the top, etc. Empirically, an average of approximately 1.281 swaps per add. | ||
Latest revision as of 13:27, 9 April 2024
This is the first time I have seen an average case analysis of the binary heap operations, and it is very helpful to know what they are since it shows that in practical real-world applications, it is probably better than many other structures mainly because of the low constants involved. Plus, the average case analysis helps analyze the average case running time of other algorithms that use the binary-heap as an auxiliary data structure.
UPDATE: The analysis of the expected number of swaps used when adding an element is incorrect. It assumes a uniform distribution of keys, but keys are certainly not uniformly distributed in a heap. In a min-heap, smaller keys are far more likely to be near the top, etc. Empirically, an average of approximately 1.281 swaps per add.
