Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|improve this question
1  
Does it work as expected? Did you test it? – Mast Oct 25 '16 at 16:46
    
@Mast-It works for several test cases that i have tested. – Kiran B.R Oct 25 '16 at 17:13
1  
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. – Eric Lippert Oct 25 '16 at 18:29
    
@Eric- Added asserts as suggested. – Kiran B.R Oct 27 '16 at 17:24
    
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? – Eric Lippert Oct 27 '16 at 17:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.