Binary heap: Difference between revisions

Revision as of 20:24, 12 October 2004

Revision as of 15:04, 13 October 2004

Line 19:

== 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 it'sits 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