4
\$\begingroup\$

Is this a correct linked list implementation of binary heap insertion? This is not a homework exercise.

public BinaryHeap insert(int value , BinaryHeap node , int count)
    {

        //1. Insert into a binary tree breadth wise( satisfy complete binary property) (left to right)
        //2. Once inserted ,fix the tree by running heapify every time a new value(non duplicate) is added.
        //3. Count represents the total no of elements in the tree. Calculate the total no of parents for given set of elements.

         int parent = (count - 1)/2;

        if (node == null)
        {
            node = new BinaryHeap();
            node.data = value;


        }

            else
        {
            if (((parent == 0) && (node.left == null)) || (parent % 2 == 1))
            {


                node.left = insert(value, node.left, parent);
                Debug.Assert(node.left != null); 
                node.left.parent = node;
                Heapify(node.left);
                if (node.right != null) // if both left and right sub tree are filled
                {
                    Debug.Assert(node.data < node.left.data && node.data < node.right.data);// heapified node  will be minimum
                }
                else // incomplete subtree withh right subtree not filled.
                {
                    Debug.Assert(node.data < node.left.data);
                }
            }

            else
            {
                Debug.Assert(node.left != null); 
                node.right = insert(value, node.right, parent);
                Debug.Assert(node.right != null); 
                node.right.parent = node;

                Heapify(node.right);
                if (node.left != null) // if both left and right sub tree are filled
                {
                    Debug.Assert(node.data < node.left.data && node.data < node.right.data);// heapified node  will be minimum
                }
                else // incomplete sub tree with right sub tree not filled.
                {
                    Debug.Assert(node.data < node.right.data);
                }

            }
        }// end of else
        // every time you add an element you run heapify to rearrange the nodes.

        return node;
    }

    public void Heapify(BinaryHeap node)

    { 
   //Bubble up until you are unable to
        if (node == null)
        {
            return;
        }

        else
        {

            if (node.parent != null && node.parent.data > node.data)
            {
                //swap the value
                int temp = node.parent.data;
                node.parent.data = node.data;
                node.data = temp;
                node = node.parent;
                Heapify(node.parent);
                return;
            }
    }
  }// end of function heapify
\$\endgroup\$
  • 2
    \$\begingroup\$ Does it work as expected? Did you test it? \$\endgroup\$ – Mast Oct 25 '16 at 16:46
  • \$\begingroup\$ @Mast-It works for several test cases that i have tested. \$\endgroup\$ – Kiran B.R Oct 25 '16 at 17:13
  • 1
    \$\begingroup\$ Add assertions as pre and post conditions. That is, you expect that something will be true before heapify runs, and there is something you expect to be true after it runs. Add assertions that fire if either of those invariants are violated. This will help readers understand the code, and also find bugs if you've accidentally violated the conditions. \$\endgroup\$ – Eric Lippert Oct 25 '16 at 18:29
  • 1
    \$\begingroup\$ Consider node.left.parent = node; Debug.Assert(node.left != null); This assertion is poorly placed. Do you see why? Suppose the assertion is ever violated; would it fire? \$\endgroup\$ – Eric Lippert Oct 27 '16 at 17:28
  • 1
    \$\begingroup\$ No, what I'm getting at is: the assertion cannot fire because the program already crashed if the left side was null. You said node.left.parent before asserting that the left side was not null. So if the left side was null, the assertion would not fire because the program is already toast. That makes the assertion useless. \$\endgroup\$ – Eric Lippert Oct 27 '16 at 19:38
3
\$\begingroup\$

It's always worth tidying up indentation and removing random blank lines (e.g. after {).


Naming: in C# it's conventional that method names are in UpperCamelCase, but even if you choose not to follow the convention it's important to be consistent. Here Heapify follows the convention but insert doesn't.

The name Heapify usually refers to taking an unstructured array of data and structuring it as a heap in linear time. The method implemented here should probably have a name like UpHeap.


It's not clear how insert is supposed to be used. Is it called passing the root of the tree? And where does count come from? It seems to me that BinaryHeap should be BinaryHeapNode and should be a private inner class of a public BinaryHeap which exposes public void Insert(int value).


        int parent = (count - 1)/2;

What does this represent? Elsewhere parent is a BinaryHeap, and it's obvious what it means, but as far as I can guess this variable is actually the size of the right subtree.


            if (((parent == 0) && (node.left == null)) || (parent % 2 == 1))

Why? I need some comments somewhere in the code to say how the tree is structured. This looks like an attempt to keep it balanced, but I'm not convinced that it works. (I suspect it should check the parity of count rather than parent). Maybe if I knew precisely what it was trying to do I could be convinced.


I don't understand the necessity of all those asserts, but IMO it would be cleaner to remove the duplication by pulling them out of the cases as

            if (node.left != null)
            {
                Debug.Assert(node.data < node.left.data);
            }
            if (node.right != null)
            {
                Debug.Assert(node.data < node.right.data);
            }

or

            Debug.Assert(node.left == null || node.data < node.left.data);
            Debug.Assert(node.right == null || node.data < node.right.data);

The recursive insert calls Heapify at each level that it touches. Heapify bubbles up. That means there's unnecessary duplication of work here.


Why is Heapify public?


if (condition)
{
    DoStuff();
}
else
{
    if (otherCondition)
    {
        OtherStuff();
    }
}

creates unnecessary indentation and vertical spacing, both of which make it harder to read the code. Rewrite as

if (condition)
{
    DoStuff();
}
else if (otherCondition)
{
    OtherStuff();
}
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.