java - 如果已添加项目的值发生变化，如何管理堆(最小堆)-6ren

java - 如果已添加项目的值发生变化，如何管理堆(最小堆)

转载作者：塔克拉玛干更新时间：2023-11-03 04:06:55

我是一名 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/

文章推荐： java - 如何在另一个图表中找到一个图表的 x,y 位置不同

文章推荐： java - Spring Boot @ExceptionHandler 隐藏异常名称

文章推荐： java - 无法为应用引擎项目创建谷歌凭据

文章推荐： javascript - 为 20 位数字间隔生成唯一且可逆的 ID

javascript - 如何在单击添加时隐藏最后一次单击(添加)按钮以及当用户单击删除按钮然后显示上一个隐藏(添加)按钮
我创建了一个用户可以添加测试的字段。这一切运行顺利我只希望当用户点击(添加另一个测试)然后上一个(添加另一个测试)删除并且这个显示在新字段中。所有运行良好的唯一问题是点击(添加另一个字段)之前添加另
java - 将数组的内容添加到 JFrame，添加 JPanel，添加 JScroll
String[] option = {"Adlawan", "Angeles", "Arreza", "Benenoso", "Bermas", "Brebant
php - 为什么我们不能使用 MAC 添加。而不是 IP 添加
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。这个问题似乎不是关于 a specific programming problem, a softwar
jquery - 添加 jQuery Nav-tab 添加 Bootstrap
我正在努力将 jQuery 滚动功能添加到 nav-tab (Bootstrap 3)。我希望用户能够选择他们想要的选项卡，并在选项卡内容中有一个可以平滑滚动到 anchor 的链接。这是我的代码，可
jquery - 添加 CSS 到 jQuery Ui Tab 添加
我正在尝试在用户登录后再添加 2 个 ui 选项卡。首先，我尝试做一个之后。 $('#slideshow').tabs('remove', '4'); $("#slideshow ul li:last
javascript - 使用 JavaScript 添加/删除元素(添加/删除带有编号 ID 和名称的字段)
我有一个包含选择元素的表单，我想通过选择添加和删除其中一些元素。这是html代码(这里也有jsfiddle http://jsfiddle.net/txhajy2w/):
ios - 添加 alpha 以查看 VS 添加 alpha 到 UIColor
正在写这个: view.backgroundColor = UIColor.white.withAlphaComponent(0.9) 等同于: view.backgroundColor = UICo
Javascript 添加
好的，如果其中有任何信息，我想将这些列添加到一起。所以说我有账户 1 2 3 . 有 4 个帐户空间，但只有 3 个帐户。我如何创建 java 脚本来添加它。最佳答案 Live Example H
添加/减去数字以查找是否可以生成数字的算法？
我想知道是否有一种有效的预制算法来确定一组数字的和/差是否可以等于不同的数字。示例: 5、8、10、2，使用 + 或 - 等于 9。5 - 8 = -3 + 10 = 7 + 2 = 9 如果有一个预
Git卡在状态/添加/提交
我似乎有一个卡住的 git repo。它卡在所有基本的添加、提交命令上，git push 返回所有内容为最新的。从其他帖子我已经完成了 git gc 和 git fsck/ 我认为基本的调试步骤是
sql - 添加 where 子句会使查询速度变慢
我的 Oracle SQL 查询如下- Q1- select hca.account_number, hca.attribute3, SUM(rcl.extended_amou
iPhone:添加 UIRequiredDeviceCapability
我正在阅读 http://developer.apple.com/iphone/library/documentation/iPhone/Conceptual/iPhoneOSProgrammingG
javascript - 添加 "more"按钮
我正在尝试添加一个“加载更多”按钮并限制下面的结果，这样投资组合页面中就不会同时加载 1000 个内容，如下所示:http://typesetdesign.com/portfolio/ 我对 PHP
javascript - 添加，使用Javascript函数添加多个文本框
我遇到这个问题，我添加了 8 个文本框，它工作正常，但是当我添加更多文本框(如 16 个文本框)时，它不会添加最后一个文本框。有人遇到过这个问题吗？提前致谢。 Live Link: JAVASCRIP
javascript - 添加/删除克隆第一行默认不删除
add/remove clone first row default not delete 添加/删除克隆第一行默认不删除&并获取正确的SrNo(例如:添加3行并在看到问题后删除SrNo.2)
javascript - 添加/删除表单中的输入
我编码this ，但删除按钮不起作用。我在控制台中没有任何错误.. var counter = 0; var dataList = document.getElementById('materi
javascript - 添加/删除类似数组的对象中的元素
我有一个类似数组的对象: [1:数组[10]、2:数组[2]、3:数组[2]、4:数组[2]、5:数组[3]、6:数组[1]] 我正在尝试删除前两个元素，执行一些操作，然后将它们再次插入到同一位置。
arrays - 添加/删除单元格时保持数组排序的最佳方法
使用的 Delphi 版本:2007 你好，我有一个 Tecord 数组 TInfo = Record Name : String; Price : Integer; end; var Info
javascript - 添加/删除小部件以及调整大小不起作用
我使用了基本的 gridster 代码，然后我声明了通过按钮添加和删除小部件的函数它工作正常但是当我将调整大小功能添加到上面的代码中时，它都不起作用(我的意思是调整大小，添加和删除小部件) 我的js代
javascript - 添加/删除上一个或下一个父级中的类
title 323 323 323 title 323 323 323 title 323 323 323 JS $(document).keydown(function(e){

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

java - 如果已添加项目的值发生变化，如何管理堆(最小堆)