如何使用显式链接（使用三重链接数据结构）实现优先级队列？

Question

我正在尝试使用三重链接数据结构实现优先级队列。我想了解如何实现sink和swim操作，因为当你使用数组时，你可以只计算该数组的索引，仅此而已。当您使用三重链接 DS 时，这没有意义。

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

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

（这是 Sedgewick 的任务）。

Answer 1

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

我写了一个面向最大优先级队列的实现，可以根据任何优先级修改。

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

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

swim() 的工作原理：这里我只是通过做 x = x.parent，并交换 x 和 x.parent 中的数据，直到 x.parent == null，或者 x.data <= x.parent ].

max() 的工作原理：它只是 returns root.data.

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

insert() 的工作原理：如果优先级队列为空，我会创建一个新根。如果它不为空，我检查 x.left 和 x.right 的大小，如果 x.left 的大小大于 x.right，我递归调用 x.right 的插入，否则我递归调用 x.left 的插入。当到达空节点时，我 return new Node(data, 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;
    }
}

如何使用显式链接（使用三重链接数据结构）实现优先级队列？

How do I implement a priority queue with explicit links (using a triply linked datastructure)?

java

algorithm

binary-tree

priority-queue

binary-search-tree