Bottom-up and Top-down Construction of a Binary Heap

The goal of this exercise is to build a valid binary heap from an initially unordered set of keys. Two different methods exist for building a valid heap. This demonstration lets you walk though both methods while using the same underlying set of keys.

You are to start by building the first heap using the standard construction. This method is based on using "upheap" to swap each newly inserted item into its correct position. The current element is highlighted in red. If you choose, you may click on the current element's parent to have those items swap places. When you feel the highlighted element is properly placed, click on the "done processing item" button to continue. When you are done building the entire heap, you may click on the "validate" button to verify its correctness.

You are to build the second heap using the bottom-up heap construction which is based on using "downheap" to swap each highlighted item into the correct position in the subtree rooted at that item. The current element is highlighted in red. If you choose, you may click on either of the current element's children to have the items swap places. When you feel the highlighted element is properly placed, click on the "done processing item" button to continue. When you are done building the entire heap, you may click on the "validate" button to verify its correctness.

If you constructed both heaps properly, you may wish to observe the following:

  • How many swaps were performed by the standard method? (there is a counter on the screen displaying this information)
  • How many swaps were performed by the bottom-up method? (there is a counter on the screen displaying this information)
  • Did the two methods produce the same heap or different heaps?

    • Michael Goldwasser