0
$\begingroup$

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness.

Firstly, I define the following procedure (pseudocode):

process_node():
    if the node has children:
        select the child node with the maximum value
        if the selected node's value is greater than the value of current node:
            swap current node with the selected node

Then I run this procedure on all non-leaf nodes going down level by level in the binary tree view of the array. So the root is processed first, then comes the first level etc. After doing this, a half of leaf nodes become smaller than all of their ancestors. Another run of the procedure on the same nodes settles the other half of the leaves. Thus, they have been put in place in the heap and can be removed from the processing.

The number of leaves is halved, and so is the number of non-leaf nodes. The procedure is run again on new non-leaves, and the process is repeated until all the elements of the array are processed.

The number of nodes on which the procedure is run starts with $N/2$ and later is halved. We get a decreasing geometric series with the sum being $O(N)$.

Are there any mistakes in my reasoning?

EDIT.

An example with 7 elements. The number of levels $L = 3$.

       1
    /    \
   2      3
  / \    / \
 4   5  6   7

Step 1. The root node is processed with process_node().

       3
    /    \
   2      1
  / \    / \
 4   5  6   7

Step 2. The nodes in the level 1 are processed. The total number of levels processed in this way is $L' = L - 1$.

       3
    /    \
   5      7
  / \    / \
 4   2  6   1

The processing of each node sifts the smallest value in the node and its direct descendants one level down. Each node thus "generates" the smallest value for its children. After steps 1 and 2 are completed, the values "2" and "1" are on their correct places. It is a half of the leaf nodes.

Step 3. Repeat steps 1 and 2. The lowest level is completely filled and can be excluded from further processing. The second lowest level can be thought of as the new "leaves".

       7
    /    \
   5      6
  / \    / \
 4   2  3   1

The heap is now fully built, but it seems to be an accident that it is constructed this early. So,

Step 4. Do steps 1 and 2 for the first $L' = L' - 1$ levels. Repeat until $L' = 0$.

$\endgroup$
  • 1
    $\begingroup$ Could you give an example of this procedure? It's hard to for me to visualize what this is doing. Maybe on $7$ or $15$ elements? It sounds like you're sifting all nodes which would take $O(n \log n)$, but I am not quite sure. $\endgroup$ – ryan Apr 19 at 16:37
  • 1
    $\begingroup$ I don't understand what you mean by "The number of leaves is halved". In a binary heap, the number of leaves is fixed and depends only on $N$; it doesn't change. Swapping elements of the array doesn't change the number of leaves. $\endgroup$ – D.W. Apr 19 at 20:00
  • $\begingroup$ @ryan I've added an example. $\endgroup$ – Alex Konrad Apr 20 at 13:28
  • $\begingroup$ So you basically sweep this operation over level 0, then over level 1, then over level 2 and so on until level $L - 1$. Then you go back and sweep this operation over level 0, then over level 1, then over level 2 and so on until level $L - 2$. So you're only sweeping over half as many nodes each time? $\endgroup$ – ryan Apr 20 at 21:09
  • 1
    $\begingroup$ We typically don't proofread arguments. $\endgroup$ – Yuval Filmus Apr 21 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.