How to define formula to determine which group does the element belong to?

Question

I am trying to build a min-max heap tree, here's an example of the tree structure:

• The tree is a complete binary tree
• The index in the array of the tree root is 0 and it contains no element.
• The left subtree is a min-heap and the right subtree is a max-heap.

When I am trying to implement the insertion, I meet a problem that I don't know whether the new element belongs to the min-heap or the max-heap by its index.

index_of_min_heap = {1, 3, 4, 7, 8, 9, 10, ...} index_of_max_heap = {2, 5, 6, 11, 12, 13, 14, ...}

How can I make a formula to determine the index is a min-heap index or a max-heap index? example :

is_min_or_max_heap(112) // return min or max

Answer 1

Please initially note that w.r.t. your definition, your min-max heap tree is also a complete binary tree (WikiPedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible).

In a complete binary tree implemented via an array -like yours- the $k$th layer has an index from $2^{k-1}-1$ to $2^{k}-2$, considering the root to be $0$th element of the array existing in $k=1$ (where your root is the null element).

So for a given index, $x$, you need to initially iterate through $k$ (starting k=$1$ where the root exists) and if for $k=k^*$ the condition $2^{k-1}-1 \le x\le 2^{k}-2$ satisfies you should stop and do as follows to know whether the index belongs to the min heap or the max heap.

Please note that you have a binary tree so in each level you can divide it into two halves. The right half belongs to the min heap and the left one belongs to the max heap. Since in each layer exists $2^{k}-2 - (2^{k-1}-1) + 1 = 2^{k-1}$ nodes, nodes with index from $2^{k^*-1}-1$ to $2^{k^*-1}-1 + \frac{2^{k^*-1}}{2} - 1= 3\times2^{k^*-2} -2$ belong to the min heap and the rest (i.e. $3\times2^{k^*-2} -1$ to $2^{k^*}-2$) belong to the max heap.

Answer 2

Personally, I like to start my indexing with 1 when representing complete binary trees. The main reason is that the computation of left and right children is very simple: the children of node $n$ are $2n$ and $2n+1$. This is just adding a 0/1 bit after the binary representation of the parent.

Also for your question this representation gives a clear answer. The second bit (after the leading 1) determines whether the child is in the left or right subtree of the root. (Combinatorically simple, but I do not know whether that is computationally feasible.)