An animation of adding elements to a heap

Posted on October 24, 2010. Filed under: Uncategorized | Tags: , , , , , , , |

Here is an animation of how elements are inserted into a heap (sometimes used to implement a prioirty queue). At the top you can see the elements arranged in a tree, at the bottom is the corresponding array representation of the heap. The correspondence between the tree nodes and the array is such that the children of array element j are stored in positions 2j+1 and 2j+2 (where the indexing starts at 0).

The algorithm corresponds to what is described in section 4.3.2 of in “The Algorithm Design Manual” by Steven Skiena. Each time an element is added, it is put into the first empty position in the array representation at the bottom. This corresponds to making the new element a child of one of the leaf nodes. Then, the element is ‘bubbled up’ (swapped with its parent) as long as it is smaller than the parent.

Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here. This demo makes use of the Trident java animation library.

Comments and suggestions are welcome !

Advertisements

Make a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: