Content deleted Content added
Line 57:
:: Removing an element (in this case, a vertex) requires finding it first, which is O(|V|), not O(log|V|) - note: you don't know the index. Relax(v) can alternatively be defined as = find key (O(|V|)) + decrease-key (O(log |V|)) = O(|V|) -- [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 22:13, 26 May 2011 (UTC)
:::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)
| |||