Does bottom up heap construction completely depend on the fact that (n+1) is a power of 2?

Question

Doesn't bottom up heap construction completely depend on the fact that (n+1) is a power of 2? (where n is the number of nodes).

For example consider the case n = 21. (n +1) is NOT a power of 2- how would this work?

You would create first insert (n+1)/2 nodes or in other words 11 nodes. You would then insert (n+1)/4 nodes to be the parents of the previously inserted nodes or in other words 5.5 nodes. But how can "half a node" be inserted? Whenever n is not a power of 2, you always arrive at a decimal amount of node insertions at some level - how do you deal with this?

I considered removing a certain amount of nodes such that the remaining nodes are a power of two, building a tree out of the remaining nodes and then bubbling the removed nodes into the tree after it has been completed. But with large amounts of nodes this becomes unfeasible: i.e. number of nodes = 1600. The closest power of 2 is 1024, meaning you would have to bubble 576 nodes, which is relatively time consuming.

Answer 1

No, there is no requirement that this happens. Remember that a binary heap may have nodes missing from its final layer. This means that in the first step, you combine the nodes in a way where you end up with a collection of heaps such that those heaps will form the last two layers of the heap. Not all of those heaps have to be complete heaps; some of them will have missing children.

If you choose the number of children to omit in a way that the remaining number of nodes is one less than a perfect power of two, you can then proceed with the bottom-up construction as usual. The result will be a complete binary heap.

Hope this helps!