Binary heap: Difference between revisions

Revision as of 01:17, 11 April 2005

Revision as of 22:54, 7 May 2005

Line 18:

== Heap operations ==

=== Adding to the heap ===

If we have a heap, and we add an element, we can perform an operation known as ''up-heap'', ''bubble-up'', or ''sift-up'' in order to restore the heap property. We can do this in [[Big O notation|O]](log ''n'') time, using a binary heap, by adding the element on the bottom level of the heap regardless, then considering the added element and its parent and swapping the element and its parent if need be until we are assured the heap property remains. We do this at maximum for each level in the tree -— the height of the tree, which is O(log ''n'').

Say we have a max-heap