Updating Heap in both direction (Prim's Algorithm)

Question

In Prim's algorithm, it is recommended to maintain the invariant in the following way :

When a vertice v is added to the MST:
  For each edge (v,w) in the unexplored tree:
      1. Delete w from the min heap.
      2. Recompute the key[w] (i.e. it's value from the unexplored tree
         to the explored one).
      3. Add the value back to the heap.

So, basically this involves deletion from the heap (and heapify which takes O(logn)) and then reinserting (again O(logn))

Instead, if I use the following approach:

For each edge (v,w) in the unexplored tree:
    1. Get the position of the node in the heap(array) using HashMap -> O(1)
    2. Update the value in place.
    3. Bubble up or bubble down accordingly. -> O(logn)

Which gives better constants than the previous one.

The controversial part is the 3rd part where Im supposed to bubble up or down.

My implementation is as follows :

public int heapifyAt(int index){
        // Bubble up
        if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
            while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
                swap(index, (int)Math.floor(index/2));
                index = (int)Math.floor(index/2);
            }
        }else{
            // Bubble down
            while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
                if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
                    //swap with left child
                    swap(index, index*2 + 1);
                    index = index*2 + 1;
                }else{
                    //swap with right child
                    swap(index, index*2 + 2);
                    index = index*2 + 2;
                }
            }
        }
        return index;
    }

And I'am plucking from the heap this way :

public AdjNode pluck(){
    AdjNode min = heap[0];
    int minNodeNumber = heap[0].nodeNumber;
    AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
    heap[0].edgeCost = INF; // set this to infinity, so it'll be at the bottom
                            // of the heap.
    heapifyat(0);
    visited.add(minNodeNumber);
    updatevertices(minNodeNumber); // Update the adjacent vertices
    return toRet;
}

And updating the plucked vertices this way :

public void updatevertices(int pluckedNode){
    for(AdjNode adjacentNode : g.list[pluckedNode]){
        if(!visited.contains(adjacentNode.nodeNumber)){  // Skip the nodes that are already visited
            int positionInHeap = map.get(adjacentNode.nodeNumber); // Retrive the position from HashMap
            if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
                heap[positionInHeap].edgeCost = adjacentNode.edgeCost; // Update if the cost is better
                heapifyAt(positionInHeap); // Now this will go bottom or up, depending on the value
            }
        }
    }
}

But when I execute it on large graph, the code fails, There are small values in the bottom of heap and large values at the top. But the heapifyAt() API seems to work fine. So I am unable to figure out is my approach wrong or my code? Moreover, if I replace the heapifyAt() API by siftDown(), i.e. construct the heap, it works fine, but it doesnt make sense calling siftDown() that takes O(n) time for every updates which can be processed in logarithmic time.

In short : Is it possible to update the values in Heap both way, or the algorithm is wrong, since that's why it is recommended to first remove the element from Heap and reinsert it.

EDIT : Complete code:

public class Graph1{
    public static final int INF = 9999999;
    public static final int NEGINF = -9999999;
    static class AdjNode{
        int nodeNumber;
        int edgeCost;
        AdjNode next;

        AdjNode(int nodeNumber, int edgeCost){
            this.nodeNumber = nodeNumber;
            this.edgeCost = edgeCost;
        }
    }

    static class AdjList implements Iterable<AdjNode>{
        AdjNode head;

        AdjList(){
        }

        public void add(int to, int cost){
            if(head==null){
                head = new AdjNode(to, cost);
            }else{
                AdjNode temp = head;
                while(temp.next!=null){
                    temp = temp.next;
                }
                temp.next = new AdjNode(to, cost);
            }
        }

        public Iterator<AdjNode> iterator(){
            return new Iterator<AdjNode>(){
                AdjNode temp = head;

                public boolean hasNext(){
                    if(head==null){
                        return false;
                    }
                    return temp != null;
                }

                public AdjNode next(){
                    AdjNode ttemp = temp;
                    temp = temp.next;
                    return ttemp;
                }

                public void remove(){
                    throw new UnsupportedOperationException();
                }

            };
        }

        public void printList(){
            AdjNode temp = head;
            if(head==null){
                System.out.println("List Empty");
                return;
            }
            while(temp.next!=null){
                System.out.print(temp.nodeNumber + "|" + temp.edgeCost + "-> ");
                temp = temp.next;
            }
            System.out.println(temp.nodeNumber + "|" + temp.edgeCost);
        }

    }


    static class Heap{
        int size;
        AdjNode[] heap;
        Graph g;
        int pluckSize;
        Set<Integer> visited = new HashSet<Integer>();
        HashMap<Integer, Integer> map = new HashMap<>();
        Heap(){

        }
        Heap(Graph g){
            this.g = g;
            this.size = g.numberOfVertices;
            this.pluckSize = size - 1;
            heap = new AdjNode[size];
            copyElements();
            constructHeap();
        }

        public void copyElements(){
            AdjList first = g.list[0];
            int k = 0;
            heap[k++] = new AdjNode(0, NEGINF); //First entry
            for(AdjNode nodes : first){
                heap[nodes.nodeNumber] = nodes;
            }

            for(int i=0; i<size; i++){
                if(heap[i]==null){
                    heap[i] = new AdjNode(i, INF);
                }
            }
        }

        public void printHashMap(){
            System.out.println("Priniting HashMap");
            for(int i=0; i<size; i++){
                System.out.println(i + " Pos in heap :" + map.get(i));
            }
            line();
        }

        public void line(){
            System.out.println("*******************************************");
        }

        public void printHeap(){
            System.out.println("Printing Heap");
            for(int i=0; i<size; i++){
                System.out.println(heap[i].nodeNumber + " | " + heap[i].edgeCost);
            }
            line();
        }

        public void initializeMap(){
            for(int i=0; i<size; i++){
                map.put(heap[i].nodeNumber, i);
            }
        }

        public void swap(int one, int two){
            AdjNode first = heap[one];
            AdjNode second = heap[two];
            map.put(first.nodeNumber, two);
            map.put(second.nodeNumber, one);

            AdjNode temp = heap[one];
            heap[one] = heap[two];
            heap[two] = temp;
        }

        public void constructHeap(){
            for(int i=size-1; i>=0; i--){
                int temp = i;
                while(heap[temp].edgeCost < heap[(int)Math.floor(temp/2)].edgeCost){
                    swap(temp, (int)Math.floor(temp/2));
                    temp = (int)Math.floor(temp/2);
                }

            }
            initializeMap();
        }

        public void updatevertices(int pluckedNode){
            for(AdjNode adjacentNode : g.list[pluckedNode]){
                if(!visited.contains(adjacentNode.nodeNumber)){
                    int positionInHeap = map.get(adjacentNode.nodeNumber);
                    if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
                        // //System.out.println(adjacentNode.nodeNumber + " not visited, Updating vertice " + heap[positionInHeap].nodeNumber + " from " + heap[positionInHeap].edgeCost + " to " + adjacentNode.edgeCost);
                        // heap[positionInHeap].edgeCost = INF;
                        // //heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
                        // int heapifiedIndex = heapifyAt(positionInHeap);             // This code follows my logic
                        // heap[heapifiedIndex].edgeCost = adjacentNode.edgeCost;      // (which doesnt work)
                        // //heapifyAt(size - 1);
                        heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
                        //heapifyAt(positionInHeap);
                        constructHeap();                                                // When replaced by SiftDown, 
                    }                                                                   // works as charm
                }
            }
        }

        public void printSet(){
            Iterator<Integer> it = visited.iterator();
            System.out.print("Printing set : [");
            while(it.hasNext()){
                System.out.print((int)it.next() + ", ");
            }
            System.out.println("]");
        }

        public AdjNode pluck(){
            AdjNode min = heap[0];
            int minNodeNumber = heap[0].nodeNumber;
            AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
            heap[0].edgeCost = INF;
            constructHeap();
            visited.add(minNodeNumber);
            updatevertices(minNodeNumber);
            return toRet;
        }

        public int heapifyAt(int index){
            if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
                while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
                    swap(index, (int)Math.floor(index/2));
                    index = (int)Math.floor(index/2);
                }
            }else{
                if(index*2 + 2 < size){
                    while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
                        if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
                            //swap with left child
                            swap(index, index*2 + 1);
                            index = index*2 + 1;
                        }else{
                            //swap with right child
                            swap(index, index*2 + 2);
                            index = index*2 + 2;
                        }
                    }
                }
            }
            return index;
        }
    }

    static class Graph{
        int numberOfVertices;
        AdjList[] list;

        Graph(int numberOfVertices){
            list = new AdjList[numberOfVertices];
            for(int i=0; i<numberOfVertices; i++){
                list[i] = new AdjList();
            }
            this.numberOfVertices = numberOfVertices;
        }

        public void addEdge(int from, int to, int cost){
            this.list[from].add(to, cost);
            this.list[to].add(from, cost);
        }

        public void printGraph(){
            System.out.println("Printing Graph");
            for(int i=0; i<numberOfVertices; i++){
                System.out.print(i + " = ");
                list[i].printList();
            }
        }

    }


    public static void prims(Graph graph, Heap heap){
        int totalMin = INF;
        int tempSize = graph.numberOfVertices;
        while(tempSize>0){
            AdjNode min = heap.pluck();
            totalMin += min.edgeCost;
            System.out.println("Added cost : " + min.edgeCost);
            tempSize--;
        }
        System.out.println("Total min : " + totalMin);
    }

    public static void main(String[] args) throws Throwable {
        Scanner in = new Scanner(new File("/home/mayur/Downloads/PrimsInput.txt"));
        Graph graph = new Graph(in.nextInt());
        in.nextInt();
        while(in.hasNext()){
            graph.addEdge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
        }
        Heap heap = new Heap(graph);
        prims(graph, heap);
    }
}

Answer 1

With a proper implementation of heap, you should be able to bubble up and down. Heap preserves a group of elements using an order that applies to both directions and bubbling up and down are essentially the same, apart from the direction in which you move.

As to your implementation, I believe you are correct but one, seemingly minor issue: indexing.

If you look around for array implementations of heap, you will notice that in most cases the root is located at index 1, instead of 0. The reason for that being, in a 1-indexed array you preserve the following relation between parent p and children c₁ and c₂.

heap[i] = p
heap[2 * i] = c1
heap[2 * i + 1] = c2

It is trivial to draw an array on a piece of paper and see that this relation holds, if you have the root at heap[1]. The children of root, at index 1, are located at indices 2 and 3. Children of the node at index 2 are at indices 4 & 5, while children of the node at index 3 are at indices 6 & 7, and so on.

This relation helps you get to the children or the parent of any node at i, without having to keep track of where they are. (i.e. parent is at floor(i/2) and children are at 2i and 2i+1)

What you seem to have tried is a 0-indexed implementation of heap. Consequently you had to use a slightly different relation given below for parent p and children c₁ and c₂.

heap[i] = p
heap[2 * i + 1] = c1
heap[2 * i + 2] = c2

This seems to be ok when accessing the children. For example, the children of root, at index 0, are located at indices 1 and 2. Children of the node at index 1 are at indices 3 & 4, while children of the node at index 2 are at indices 5 & 6, and so on. However there is a pickle when accessing the parent of a node. If you consider node 3 and take floor(3/2), you do get index 1, which is the parent of 1. However, if you take the node at index 4, floor(4/2) gives you index 2, which is not the parent of the node at index 4.

Obviously, this adaptation of the index relationship between a parent and its children does not work for both children. Unlike the 1-indexed heap implementation, you can not treat both children the same while accessing their parents. Therefore, the problem lies specifically in your bubbling up part, without necessarily being related to bubbling up operation. As a matter of fact, though I haven't tested your code, the bubbling up portion of heapifyAt function seems to be correct.(i.e. except the indexing, of course)

Now, you may keep using a 0-indexed heap and adapt your code so that whenever you are looking for a node's parent, you implicitly check whether it is the right (i.e. not as in correct but as in the opposite of left) child of that parent and use floor((i-1)/2) if it is. Checking whether a node is the right child is trivial: just look if it is even or not. (i.e. as you index right children with 2i + 2, they will always be even)

However I recommend you take a different approach and instead use a 1-indexed array implementation of heap. The elegance of the array implementation of heap is that you can treat each node the same and you don't have to do anything different based on its index or location, with the root of the heap perhaps being the only possible exception to this.