java - 使用优先级队列作为最小堆

Question

当试图解决这个问题时https://www.hackerrank.com/challenges/cut-the-tree我试图总是挑选和切割一片叶子，然后将它的重量结合到它连接的节点上。我使用 PriorityQueue 来存储所有节点，并使用相邻节点的大小作为优先级。但是当我尝试一些测试用例时，似乎违反了优先级队列属性，这意味着非叶节点可能出现在叶节点之前。 PriorityQueue 会自动更新自己还是我应该调用一些函数来更新它。我的临时解决方案是使用一个列表来存储所有的叶子。

以下是我的代码:

public class Solution {
    private static class Node implements Comparable<Node> {
        int index;
        int value;
        Map<Integer, Node> adj;

        public Node(int index, int value) {
            this.index = index;
            this.value = value;
            this.adj = new HashMap<Integer, Node>();
        }

        @Override
        public int compareTo(Node n) {
            return adj.size() - n.adj.size();
        }
    }

    public static void main(String[] args) {

        BufferedReader br = null;
        try {
            br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));

            int total = 0;

            int N = Integer.parseInt(br.readLine());
            String[] strs = br.readLine().split(" ");
            HashMap<Integer, Node> nodes = new HashMap<Integer, Node>();

            for (int i = 0; i < N; i++) {
                int value = Integer.parseInt(strs[i]);
                nodes.put(i, new Node(i, value));
                total += value;
            }

            for (int i = 0; i < N - 1; i++) {
                strs = br.readLine().split(" ");
                int n1 = Integer.parseInt(strs[0]) - 1;
                int n2 = Integer.parseInt(strs[1]) - 1;

                nodes.get(n1).adj.put(n2, nodes.get(n2));
                nodes.get(n2).adj.put(n1, nodes.get(n1));
            }

            // PriorityQueue<Node> pq = new PriorityQueue<Node>(nodes.values());
            // while (!pq.isEmpty()) {
            // Node n = pq.poll();
            // System.out.println(n.index + " " + n.adj.size());
            // }
            // NOTE: java's PriorityQueue doesn't support update, cannot use it
            // LAME DESIGN. use a LinkedList instead

            List<Node> leaves = new LinkedList<Node>();
            for (Node node : nodes.values()) {
                if (node.adj.size() == 1) {
                    leaves.add(node);
                }
            }

            int minDiff = Integer.MAX_VALUE;

            while (!leaves.isEmpty()) {
                // get a leaf node
                // Node leaf = pq.poll();
                Node leaf = leaves.get(0);

                leaves.remove(0);
                if (leaf.adj.size() <= 0)// last node
                    break;

                int diff = Math.abs((total - leaf.value) - leaf.value);
                if (diff < minDiff)
                    minDiff = diff;

                // combind leaf to it's connection
                Node conn = null;
                for (Node node : leaf.adj.values()) {
                    conn = node;
                }

                conn.value += leaf.value;
                conn.adj.remove(leaf.index);
                if (conn.adj.size() == 1)
                    leaves.add(conn);
                nodes.remove(leaf.index);
            }

            System.out.println(minDiff);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

谢谢。

Answer 1

标准的 Java PriorityQueue 不支持更新。如果您需要删除项目，那么您必须实现自己的 minHeap。当您删除堆中的某些项目时调用 heapify。

可以找到实现和解释here !