java - 如何使用显式链接(使用三重链接数据结构)实现优先级队列？

Question

我正在尝试使用三重链接数据结构来实现优先级队列。我想了解如何实现sink 和swim 操作，因为当您使用数组时，您只需计算该数组的索引，然后就是这样。当您使用三重链接的 DS 时，这没有意义。

我还想了解如何在正确的位置正确插入一些东西，因为当你使用数组时，你可以只插入最后并进行游泳操作，这会将所有内容放入正确的位置，我如何准确计算链接 DS 中的“结束”？

另一个问题是删除具有最高优先级的元素。为此，对于数组实现，我们只需将最后一个元素与第一个(根)元素交换，然后在移除最后一个元素后，我们下沉第一个元素。

(这是 Sedgewick 的任务)。

Answer 1

我发布这个是为了防止有人在 Sedgewick 做这个练习时遇到困难，因为他没有提供解决方案。

我已经为最大优先级队列写了一个实现，它可以根据任何优先级进行修改。

我所做的是为二叉树的每个子树分配一个大小，可以递归地定义为 size(x.left) + size(x.right) + 1。我这样做确实能够找到最后一个插入的节点，能够以正确的顺序插入和删除最大值。

sink() 的工作原理: 与数组的实现相同。我们只是比较 x.left 和 x.right，看看哪个更大，然后交换 x 和 max(x.left, x.right) 中的数据，向下移动直到我们遇到一个节点，其数据 <= x。数据或没有任何子节点的节点。

swim() 的工作原理: 在这里，我只是通过执行 x = x.parent，并交换 x 和 x.parent 中的数据，直到 x.parent == null，或 x.data <= x.parent。

max() 的工作原理: 它只返回 root.data。

delMax() 的工作原理: 我将最后插入的节点保存在一个单独的字段中，称为 lastInserted。因此，我首先将 root.data 与 lastInserted.data 交换。然后，我通过从其父项中取消对它的引用来删除 lastInserted。然后我将 lastInserted 字段重置为之前插入的节点。此外，我们一定不要忘记将从根到删除节点的路径上的每个节点的大小都减少 1。然后我将根数据下沉。

insert() 的工作原理: 如果优先级队列为空，我会创建一个新根。如果它不为空，我检查 x.left 和 x.right 的大小，如果 x.left 的大小大于 x.right，我递归调用 insert for x.right，否则我递归调用 insert for x.left。当到达空节点时，我返回新节点(数据，1)。完成所有递归调用后，我增加了从根到新插入节点的路径上所有节点的大小。

这是 insert() 的图片:

这是我的java代码:

public class LinkedPQ<Key extends Comparable<Key>>{
    private class Node{
        int N;
        Key data;
        Node parent, left, right;
        public Node(Key data, int N){
            this.data = data; this.N = N;
        }
    }
    // fields
    private Node root;
    private Node lastInserted;
    //helper methods
    private int size(Node x){
        if(x == null) return 0;
        return x.N;
    }
    private void swim(Node x){
        if(x == null) return;
        if(x.parent == null) return; // we're at root
        int cmp = x.data.compareTo(x.parent.data);
        if(cmp > 0){
            swapNodeData(x, x.parent);
            swim(x.parent);
        }
    }
    private void sink(Node x){
        if(x == null) return;
        Node swapNode;
        if(x.left == null && x.right == null){
            return;
        }
        else if(x.left == null){
            swapNode = x.right;
            int cmp = x.data.compareTo(swapNode.data);
            if(cmp < 0)
                swapNodeData(swapNode, x);
        } else if(x.right == null){
            swapNode = x.left;
            int cmp = x.data.compareTo(swapNode.data);
            if(cmp < 0)
                swapNodeData(swapNode, x);
        } else{
            int cmp = x.left.data.compareTo(x.right.data);
            if(cmp >= 0){
                swapNode = x.left;
            } else{
                swapNode = x.right;
            }
            int cmpParChild = x.data.compareTo(swapNode.data);
            if(cmpParChild < 0) {
                swapNodeData(swapNode, x);
                sink(swapNode);
            }
        }
    }
    private void swapNodeData(Node x, Node y){
        Key temp = x.data;
        x.data = y.data;
        y.data = temp;
    }
    private Node insert(Node x, Key data){
        if(x == null){
            lastInserted = new Node(data, 1);
            return lastInserted;
        }
        // compare left and right sizes see where to go
        int leftSize = size(x.left);
        int rightSize = size(x.right);

        if(leftSize <= rightSize){
            // go to left
            Node inserted = insert(x.left, data);
            x.left = inserted;
            inserted.parent = x;
        } else{
            // go to right
            Node inserted = insert(x.right, data);
            x.right = inserted;
            inserted.parent = x;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    private Node resetLastInserted(Node x){
        if(x == null) return null;
        if(x.left == null && x.right == null) return x;
        if(size(x.right) < size(x.left))return resetLastInserted(x.left);
        else                            return resetLastInserted(x.right);
    }
    // public methods
    public void insert(Key data){
        root = insert(root, data);
        swim(lastInserted);
    }
    public Key max(){
        if(root == null) return null;
        return root.data;
    }
    public Key delMax(){
        if(size() == 1){
            Key ret = root.data;
            root = null;
            return ret;
        }
        swapNodeData(root, lastInserted);
        Node lastInsParent = lastInserted.parent;
        Key lastInsData = lastInserted.data;
        if(lastInserted == lastInsParent.left){
            lastInsParent.left = null;
        } else{
            lastInsParent.right = null;
        }

        Node traverser = lastInserted;

        while(traverser != null){
            traverser.N--;
            traverser = traverser.parent;
        }

        lastInserted = resetLastInserted(root);

        sink(root);

        return lastInsData;
    }
    public int size(){
        return size(root);
    }
    public boolean isEmpty(){
        return size() == 0;
    }
}