我是一名 Java 开发人员(但来自非 CS/IT 教育背景)。我对算法产生了兴趣，目前我正在尝试实现用于计算 MST 的 Prim 算法。我告诉您这些是为了让您了解上下文，但我的问题与 MST 无关。
我已经实现了我自己的 MinHeap 而不是使用 Java.util.PriorityQueue(尽管即使我更改了我的代码并使用它，我也面临着我前面提到的同样的问题)。
我将项目添加到堆中，但决定比较的项目的值即使在项目已添加到堆中后也会发生变化。现在，一旦值更改，堆就不会更改，因此在删除该项目时，我会弹出错误的项目。
如何解决这种情况..
我粘贴我的代码以供引用。我在我的 MinHeap 中添加 Vertex 类型的项目。每个 Vertex 都有一个关联的“int cost”，用于比较 Vertex 的两个对象。现在我在堆中添加 Vertex 对象，并根据“成本”的当前值调整堆，但是一旦添加 Vertex 对象，如果它的成本发生变化，那么我需要帮助如何调整并将其反射(reflect)在我的堆中.请在这方面帮助我，如果我走错了方向，也请纠正我。
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 all the keys to the 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;
}
}
}
}
最佳答案
感谢 friend 花时间回答我的问题，但我认为我在实现过程中几乎没有错误，因此我得到了错误的答案。
我在将顶点添加到 MinHeap 时更正了它的状态
我修正了输出MST边缘的逻辑，得到了正确答案....
最重要的是 Karthik(非常感谢他)建议移除并重新添加其“成本”在堆中发生变化的项目。我实际上应用了冒泡方法，而不是删除并再次添加，这是有效的!!
修改以上 3 点后，我的代码可以正常工作。
还有@Karthik，我没有用于删除之前和之后的两种方法，而是我有一种用于添加项目时(在最后，我使用方法 heapifyAfterAdd() 和其他用于当我删除第一个项目时我使用 heapifyAfterRemove() )
请在更正后找到我的代码。
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 all the keys to the 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 up this Node in the 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 i = 0;
for (; i < 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 i = 0;
for (; i < 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;
}
}
}
}
关于java - 如果已添加项目的值发生变化，如何管理堆(最小堆)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31232077/