University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
Bubble Up and Bubble Down
Revised September 27, 2005
In the famous and hilarious Pulitzer Prize winning Broadway
musical
How to Succeed in Business Without Really Trying, the
protagonist, J. Pierpont Finch, starts working for World Wide Wickets
in the mailroom. He then advances to Chairman of the Board in a
sequence of moves, each time by displacing the person already in the
position that he wants. We could call each of his promotions a
bubble up move.
If a heap is implemented as a binary tree, the operator
bubble up is defined recursively. If x is an item
in the heap, bubbleUp(x) does nothing if x is already at
the root, or if parent(x) is at least as "good" (which could
mean small, large, or something else) as x.
If x is better than parent(x), then x exchanges
position with its parent, and then bubbleUp(x) is recursively
executed on the same x (not the same position in the heap).
bubbleDown(x) is similar, but in reverse. If x has
a child which is better than x, that child exchanges with x,
and then bubbleDown(x) is executed again.
If x has two children that are better than x, it is
important to exchange with the better of the two.