Is it possible to build a heap from the root to the leaves?

Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays.

I've been looking for a way to implement a heap as an actual tree (call it pointers to structs, cons cells etc.) This would also imply building the heap from the root to the leaves (since it won't be practical to hold references to all the leaves).

With some effort I'm able to make the resulting heap to arrange the nodes s.t. the parent is greater than the children, but I cannot think of a way to also balance it.

If you are interested, the motivation for this exercise is: Prolog and its dialects don't really have arrays (they kind of do, but they are almost immutable). Besides, in languages where persistent data structures are a big deal, the usual construction of heap would be problematic.

Idea #1

I have a feeling that rotating (switching left and right nodes places) may take care of balancing (still need to try this).

Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array).

There is a very cute data structure (on the implementation level) for priority queues that is based on binary trees, has the same heap ordering of keys, but is not perfectly balanced. They are called leftist trees.
Arbitrary leftist trees can be merged efficiently.
This efficiency is obtained by forcing a height balance between the two subtrees of a node. The shortest distance to a leaf is the measure for this balance.

Perhaps these leftist trees are a better binary tree implementation for priority queues than heaps (which are arrays disguised as trees)?

StackExchange Computer Science Q#55081, answer score: 4