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 orange. 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 "Next Node" button to continue. When you feel the entire process is complete, click on the "Validate" button.
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 orange. 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 "Next Node" button to continue. When you feel the entire process is complete, click on the "Validate" button.
If you constructed both heaps properly, you may wish to observe the following:
Credits: This software was originally designed as a Java applet by Michael Goldwasser. The current version of this software was implemented in 2015 by Nick Lewchenko using Haskell with the JQuery and Canvas libraries from the GHCJS project as well as the Reactive-banana library. The source code for the project is hosted at https://github.com/RoboNickBot/interactive-tree-demos.