Content deleted Content added
Line 59:
:::If you don't know the index and have to search sequentially for it, you're doing it wrong. In this case, you do know the index: it's always at the front of the heap. And more generally if you want to find the position of a vertex in a heap (say for decrease key operations) you can simply maintain an index for each vertex that stores its position in the heap, and change these indexes whenever you change the heap. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:52, 26 May 2011 (UTC)
:::: the decrease-key operation I pointed out is not about removing from top, but a step that happens in between step 16 and 19 in pseudo code (it's implied, but rather should be written down for clarity). Also, it's not about being "wrong". Removing a non-min element from a binary heap can not be done below O(n) without datastructure augmentation as you just described, in which case the statement in the article "With a binary heap, the algorithm requires O((|E| + |V|)log |V|) time ..." is therefore wrong verbatim when applied to the pseudo code. At best, it's insufficient to describe a casual reader how one arrived at O((|E| + |V|)log |V|) as algorithm's performance. I think, the article should make this clarification and mention performance of both non-augmented and augmented structure. [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 10:03, 28 May 2011 (UTC)
:::: Okay, I have fixed the article by (1) adding step 19 explaining the need of decrease-key operation and (2) explaining runtime with and without the extra indexing. I believe this is much more clear now. Thanks for you inputs.
| |||