java - How to manage Heap (Min heap) if the value of already added item changes -
i java developer ( non cs/it educational background). have developed interest in algorithms , trying implement prim's algorithm calculating mst. have told in order let know context question independent of mst.
i have implemented own minheap instead of using java.util.priorityqueue (although when changed code , used facing same problem have mentioned ahead).
i add items heap value of item deciding comparison can change after items have been added in heap. once value changes heap not changed , hence upon removing item wrong item popped out.
how tackle situation..
i pasting code reference. adding items of type vertex in minheap. each vertex has 'int cost' associated used compare 2 objects of vertex. add object of vertex in heap , heap adjusted per current value of 'cost' once object of vertex added if cost changed want how adjust , reflected in heap. please me in regards , please correct me if going in wrong direction.
public class mstrevisited { public static void main(string[] args) { graph graph = new graph(6); graph.addnode('a'); graph.addnode('b'); graph.addnode('c'); graph.addnode('d'); graph.addnode('e'); graph.addnode('f'); graph.addedege('a', 'b', 4); graph.addedege('a', 'f', 2); graph.addedege('b', 'f', 3); graph.addedege('b', 'c', 6); graph.addedege('c', 'f', 1); graph.addedege('c', 'd', 3); graph.addedege('d', 'e', 2); graph.addedege('f', 'e', 4); graph.applyprimalgo(); } public static class graph { private vertex verticies[]; private int maxsize; private int size; private hashmap map; private minheap q; public graph(int maxsize) { this.maxsize = maxsize; verticies = new vertex[maxsize]; map = new hashmap(maxsize); q = new minheap(maxsize); } public void addnode(char data) { verticies[size] = new vertex(data, size); map.put(data, size); size++; } public void addedege(char sourcedata, char destinationdata, int weight) { int sourceindex = map.get(sourcedata); int destinationindex = map.get(destinationdata); verticies[sourceindex].adj = new neighbour(destinationindex, weight, verticies[sourceindex].adj); verticies[destinationindex].adj = new neighbour(sourceindex,weight, verticies[destinationindex].adj); } public void applyprimalgo() { // add keys q primedege pe = null; vertex vertex = verticies[0]; vertex.cost = 0; vertex.state = vertex.in_q; q.add(vertex); while(!q.isempty()){ vertex poppedvertex = q.remove(); poppedvertex.state = vertex.visited; neighbour temp = poppedvertex.adj; while(temp != null){ vertex adjvertex = verticies[temp.index]; if(adjvertex.state != vertex.visited){ if(poppedvertex.parentindex != -1){ char source = verticies[poppedvertex.index].data; char destination = verticies[adjvertex.index].data; pe = new primedege(source, destination, pe); } if(adjvertex.cost > temp.weight){ adjvertex.cost = temp.weight; adjvertex.parentindex = poppedvertex.index; } if(adjvertex.state != vertex.in_q){ q.add(adjvertex); } } temp = temp.next; } } primedege temp = pe; while(temp != null){ system.out.print("("+temp.source+","+temp.destination+") "); temp = temp.next; } system.out.println(); } private static class primedege{ public char source; public char destination; private primedege next; public primedege(char source, char destination, primedege next){ this.source = source; this.destination = destination; this.next = next; } } public static class minheap { private vertex[] items; private int maxsize; private int size; public minheap(int maxsize) { this.maxsize = maxsize; items = new vertex[maxsize]; } public void add(vertex item) { items[size] = item; heapifyafteradd(); size++; } private void swap(int index1, int index2) { vertex temp = items[index1]; items[index1] = items[index2]; items[index2] = temp; } private void heapifyafteradd() { int currindex = size; vertex curritem = items[currindex]; int parentindex = currindex / 2; vertex parentitem = items[parentindex]; while (curritem.compareto(parentitem) == -1) { swap(parentindex, currindex); currindex = parentindex; curritem = items[currindex]; parentindex = currindex / 2; parentitem = items[parentindex]; } } public vertex remove() { vertex vertex = items[0]; swap(0, size - 1); items[size-1] = null; size--; heapifyafterremove(); return vertex; } private void heapifyafterremove() { int currindex = 0; vertex curritem = items[currindex]; int childindex; vertex childitem; int left = 2 * currindex + 1; int right = 2 * currindex + 2; if (left > size - 1) { return; } if (right > size - 1) { childindex = left; } else if (items[left].compareto(items[right]) == -1) { childindex = left; } else { childindex = right; } childitem = items[childindex]; while (childitem.compareto(curritem) == -1) { swap(currindex, childindex); currindex = childindex; curritem = items[currindex]; left = 2 * currindex + 1; right = 2 * currindex + 2; if (left > size - 1) { return; } if (right > size - 1) { childindex = left; } else if (items[left].compareto(items[right]) == -1) { childindex = left; } else { childindex = right; } childitem = items[childindex]; } } public boolean isempty() { return size == 0; } } public static class hashmap { private mapnode[] map; private char[] keyset; private int maxsize; private int size; public hashmap(int maxsize) { this.maxsize = maxsize; map = new mapnode[maxsize]; keyset = new char[maxsize]; } private static class mapnode { char key; int value; mapnode next; public mapnode(char key, int value, mapnode next) { this.key = key; this.value = value; this.next = next; } } public int hash(char key) { return 31 * key; } public int getmapindexofkey(char key) { return hash(key) % maxsize; } public void put(char key, int value) { int index = getmapindexofkey(key); map[index] = new mapnode(key, value, map[index]); keyset[index] = key; size++; } public int get(char key) { int index = getmapindexofkey(key); mapnode temp = map[index]; while (temp != null) { if (temp.key == key) { break; } } if (temp != null) { return temp.value; } else { return -1; } } public char[] keyset() { return keyset; } } public static class vertex { public static final int new = 0; public static final int in_q = 1; public static final int visited = 2; private int state = new; private int cost = integer.max_value; private char data; private neighbour adj; private int index; private int parentindex = -1; public int compareto(vertex other) { if (cost < other.cost) { return -1; } if (cost > other.cost) { return 1; } return 0; } public vertex(char data, int index) { this.data = data; this.index = index; } public void addadjacentvertex(neighbour adj) { this.adj = adj; } public void updatecost(int newcost, int parentindex){ this.cost = newcost; this.parentindex = parentindex; } } public static class neighbour { private neighbour next; private int index; private int weight; public neighbour(int index,int weight, neighbour next) { this.next = next; this.index = index; this.weight = weight; } } } }
thanks friends investing time question, figured had few mistakes in implementation due getting wrong answer.
i corrected state of vertex when added minheap
i corrected logic of outputting edge of mst , got correct answer....
most important suggested karthik (many him) remove , re-add item 'cost' changes while being in heap. applied bubble approach instead of removing , again adding worked !!
after modifying above 3 points code working expect work.
also @karthik not have 2 methods before , after remove rather have 1 when add item ( in last , use method heapifyafteradd() , other when remove 1st item use heapifyafterremove() )
please find below code after corrections.
public class mstrevisited { public static void main(string[] args) { graph graph = new graph(6); /* * graph.addnode('a'); graph.addnode('b'); graph.addnode('c'); * graph.addnode('d'); graph.addnode('e'); graph.addnode('f'); * graph.addedege('a', 'b', 4); graph.addedege('a', 'f', 2); * graph.addedege('b', 'f', 3); graph.addedege('b', 'c', 6); * graph.addedege('c', 'f', 1); graph.addedege('c', 'd', 3); * graph.addedege('d', 'e', 2); graph.addedege('f', 'e', 4); */ graph.addnode('a'); graph.addnode('b'); graph.addnode('c'); graph.addnode('d'); graph.addedege('a', 'b', 4); graph.addedege('a', 'c', 2); graph.addedege('b', 'c', 1); graph.addedege('b', 'd', 2); graph.addedege('c', 'd', 3); graph.applyprimalgo(); } public static class graph { private vertex verticies[]; private int maxsize; private int size; private hashmap map; private minheap q; public graph(int maxsize) { this.maxsize = maxsize; verticies = new vertex[maxsize]; map = new hashmap(maxsize); q = new minheap(maxsize); } public void addnode(char data) { verticies[size] = new vertex(data, size); map.put(data, size); size++; } public void addedege(char sourcedata, char destinationdata, int weight) { int sourceindex = map.get(sourcedata); int destinationindex = map.get(destinationdata); verticies[sourceindex].adj = new neighbour(destinationindex, weight, verticies[sourceindex].adj); verticies[destinationindex].adj = new neighbour(sourceindex, weight, verticies[destinationindex].adj); } public void applyprimalgo() { // add keys q primedege pe = null; vertex vertex = verticies[0]; vertex.cost = 0; vertex.state = vertex.in_q; q.add(vertex); while (!q.isempty()) { vertex poppedvertex = q.remove(); poppedvertex.state = vertex.visited; neighbour temp = poppedvertex.adj; if (poppedvertex.parentindex != -1) { char source = verticies[poppedvertex.index].data; char destination = verticies[poppedvertex.parentindex].data; pe = new primedege(source, destination, pe); } while (temp != null) { vertex adjvertex = verticies[temp.index]; if (adjvertex.state != vertex.visited) { if (adjvertex.cost > temp.weight) { adjvertex.cost = temp.weight; adjvertex.parentindex = poppedvertex.index; } if (adjvertex.state != vertex.in_q) { q.add(adjvertex); adjvertex.state = vertex.in_q; } else { // bubble node in heap q.bubbleup(adjvertex); } } temp = temp.next; } } primedege temp = pe; while (temp != null) { system.out.print("(" + temp.source + "," + temp.destination + ") "); temp = temp.next; } system.out.println(); } private static class primedege { public char source; public char destination; private primedege next; public primedege(char source, char destination, primedege next) { this.source = source; this.destination = destination; this.next = next; } } public static class minheap { private vertex[] items; private int maxsize; private int size; public minheap(int maxsize) { this.maxsize = maxsize; items = new vertex[maxsize]; } public void bubbleup(vertex vertex) { // @todo int = 0; (; < size; i++) { if (items[i] == vertex) { break; } } if (i < size) { int currentindex = i; vertex currentitem = items[currentindex]; int parentindex = (currentindex-1) / 2; vertex parentitem = items[parentindex]; while (currentitem.compareto(parentitem) == -1) { swap(currentindex, parentindex); currentindex = parentindex; currentitem = items[currentindex]; parentindex = (currentindex-1) / 2; parentitem = items[parentindex]; } } } public void add(vertex item) { items[size] = item; heapifyafteradd(); size++; } private void swap(int index1, int index2) { vertex temp = items[index1]; items[index1] = items[index2]; items[index2] = temp; } private void heapifyafteradd() { int currindex = size; vertex curritem = items[currindex]; int parentindex = (currindex-1) / 2; vertex parentitem = items[parentindex]; while (curritem.compareto(parentitem) == -1) { swap(parentindex, currindex); currindex = parentindex; curritem = items[currindex]; parentindex = (currindex-1) / 2; parentitem = items[parentindex]; } } public vertex remove() { return remove(0); } public vertex remove(vertex vertex) { int = 0; (; < size; i++) { if (items[i] == vertex) { break; } } if (i < size) { return remove(i); } return null; } private vertex remove(int index) { vertex vertex = items[index]; swap(index, size - 1); items[size - 1] = null; size--; heapifyafterremove(index); return vertex; } private void heapifyafterremove(int index) { int currindex = index; vertex curritem = items[currindex]; int childindex; vertex childitem; int left = 2 * currindex + 1; int right = 2 * currindex + 2; if (left > size - 1) { return; } if (right > size - 1) { childindex = left; } else if (items[left].compareto(items[right]) == -1) { childindex = left; } else { childindex = right; } childitem = items[childindex]; while (childitem.compareto(curritem) == -1) { swap(currindex, childindex); currindex = childindex; curritem = items[currindex]; left = 2 * currindex + 1; right = 2 * currindex + 2; if (left > size - 1) { return; } if (right > size - 1) { childindex = left; } else if (items[left].compareto(items[right]) == -1) { childindex = left; } else { childindex = right; } childitem = items[childindex]; } } public boolean isempty() { return size == 0; } } public static class hashmap { private mapnode[] map; private char[] keyset; private int maxsize; private int size; public hashmap(int maxsize) { this.maxsize = maxsize; map = new mapnode[maxsize]; keyset = new char[maxsize]; } private static class mapnode { char key; int value; mapnode next; public mapnode(char key, int value, mapnode next) { this.key = key; this.value = value; this.next = next; } } public int hash(char key) { return 31 * key; } public int getmapindexofkey(char key) { return hash(key) % maxsize; } public void put(char key, int value) { int index = getmapindexofkey(key); map[index] = new mapnode(key, value, map[index]); keyset[index] = key; size++; } public int get(char key) { int index = getmapindexofkey(key); mapnode temp = map[index]; while (temp != null) { if (temp.key == key) { break; } } if (temp != null) { return temp.value; } else { return -1; } } public char[] keyset() { return keyset; } } public static class vertex { public static final int new = 0; public static final int in_q = 1; public static final int visited = 2; private int state = new; private int cost = integer.max_value; private char data; private neighbour adj; private int index; private int parentindex = -1; public int compareto(vertex other) { if (cost < other.cost) { return -1; } if (cost > other.cost) { return 1; } return 0; } public vertex(char data, int index) { this.data = data; this.index = index; } public void addadjacentvertex(neighbour adj) { this.adj = adj; } public void updatecost(int newcost, int parentindex) { this.cost = newcost; this.parentindex = parentindex; } } public static class neighbour { private neighbour next; private int index; private int weight; public neighbour(int index, int weight, neighbour next) { this.next = next; this.index = index; this.weight = weight; } } } }
Comments
Post a Comment