插入 O(log n) 的动态堆实现

Question

我正在尝试在 Java 中实现一个最小堆，但是在研究复杂性和实际实现之间，我意识到我不清楚如何将 O (log n) 插入到堆中如果使用动态数组（例如 ArrayList）作为基础结构，则可以。

我正确理解堆中的插入操作是 O(log n)，因为我们在数组末尾添加新项，并且我们将每个项与其父项进行交换，最多进行 log n 次交换。

但理论上只有当你有一个足够大的基础结构可以插入新元素时，这才有效：如果我们需要增长数组，操作将花费 O(n)。我知道在 ArrayList 中添加元素的时间复杂度为 O(1)，但我想知道是否可以通过真正的 O(log n) 插入操作来实现堆。

我可以使用 linkedList 在插入中完成 O(1)，但这意味着其他堆操作（如删除）将不再具有 O(log n) 复杂度。

我也可以使用固定数组，但这不允许在堆中插入您想要的许多元素。

还有别的办法吗？感谢大家

Answer 1

您可以使用既是双向链表的一部分又是线程二叉树的一部分的节点来实现堆。

堆维护对根（头）和尾节点的引用。

所以我们可以想象一个节点有5个指针：prev、next、left、right、parent。但是，我们不需要将 right 存储为 - 当它存在时 - 它等于 left.next.

那么基本操作如下：

提取分钟：
- 记住根的值
- 获取最后一个节点 (tail)，将其值复制到根，然后删除该节点。
- 执行筛选操作以恢复堆属性。
- Return第一步的值
添加
- 创建一个具有给定值的节点并将其作为最后一个节点（和最后一个子节点）插入，因此它变为 tail。
- 执行向上冒泡操作恢复堆属性。

这是 Java 中的一个实现：

public class Node {
    int value;
    Node prev = null;
    Node next = null;
    Node parent = null;
    Node left = null;
    
    public Node(int val) { value = val; }
}

class MinHeap {
    Node root = null;
    Node tail = null;
    
    void insert(int value) {
        Node node = new Node(value);
        if (root == null) {
            root = node;
            tail = node;
        } else {
            // Insert node into tree
            Node parent = tail.parent != null ? tail.parent : root;
            if (parent.left != null && parent.left.next != null) {
                parent = parent.next;
            }
            if (parent.left == null) {
                parent.left = node;
            }
            node.parent = parent;
            // Insert node into doubly linked list
            node.prev = tail;
            tail.next = node;
            tail = node;
            // Restore heap property
            bubbleUp(node);
        }
    }
    
    Integer extract() {
        if (root == null) return null;
        int value = root.value;
        Node node = tail;
        if (node == root) { // Heap has only one node
            root = null;
            tail = null;
            return value;
        }
        // Remove node from tree
        if (node.parent.left == node) {
            node.parent.left = null;
        }
        // Remove node from doubly linked list
        tail = node.prev;
        tail.next = null;
        // Restore heap property
        root.value = node.value;
        bubbleDown(root);
        return value;
    }
    
    void bubbleUp(Node node) {
        int value = node.value;
        while (node.parent != null && node.parent.value > value) {
            node.value = node.parent.value;
            node = node.parent;
        }
        node.value = value;
    }
    
    void bubbleDown(Node node) {
        int value = node.value;
        while (node.left != null) {
            Node child = node.left;
            if (child.next != null && child.next.value < child.value) {
                child = child.next; // Right child
            }
            if (child.value >= value) break;
            node.value = child.value;
            node = child;
        }
        node.value = value;
    }
}

    public static void main(final String[] args) {
        // Demo
        MinHeap heap = new MinHeap();
        heap.insert(9);
        heap.insert(5);
        heap.insert(3);
        heap.insert(6);
        heap.insert(7);
        heap.insert(2);
        heap.insert(8);
        heap.insert(1);
        heap.insert(4);
        
        while (heap.root != null) {
            System.out.print(heap.extract() + " ");
        }
        System.out.println();
    }

这里和可运行的一样Java脚本片段：

class Node {
    constructor(value) {
        this.value = value;
        this.prev = null;
        this.next = null;
        this.parent = null;
        this.left = null;
    }
}

class MinHeap {
    constructor() {
        this.root = null;
        this.tail = null;
    }
    insert(value) {
        let node = new Node(value);
        if (!this.root) {
            this.root = node;
            this.tail = node;
        } else {
            // Insert node into tree
            let parent = this.tail.parent || this.root;
            if (parent.left?.next) {
                parent = parent.next;
            }
            if (!parent.left) {
                parent.left = node;
            }
            node.parent = parent;
            // Insert node into doubly linked list
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
            // Restore heap property
            this.bubbleUp(node);
        }
    }
    extract() {
        if (!this.root) return;
        let value = this.root.value;
        let node = this.tail;
        if (node == this.root) { // Heap has only one node
            this.root = null;
            this.tail = null;
            return value;
        }
        // Remove node from tree
        if (node.parent.left === node) {
            node.parent.left = null;
        }
        // Remove node from doubly linked list
        this.tail = node.prev;
        this.tail.next = null;
        // Restore heap property
        this.root.value = node.value;
        this.bubbleDown(this.root);
        return value;
    }
    bubbleUp(node) {
        let value = node.value;
        while (node.parent && node.parent.value > value) {
            node.value = node.parent.value;
            node = node.parent;
        }
        node.value = value;
    }
    bubbleDown(node) {
        let value = node.value;
        while (node.left) {
            let child = node.left;
            if (child.next && child.next.value < child.value) {
                child = child.next; // Right child
            }
            if (child.value >= value) break;
            node.value = child.value;
            node = child;
        }
        node.value = value;
    }
}

// Demo
let heap = new MinHeap;
heap.insert(9);
heap.insert(5);
heap.insert(3);
heap.insert(6);
heap.insert(7);
heap.insert(2);
heap.insert(8);
heap.insert(1);
heap.insert(4);

while (heap.root) {
    console.log(heap.extract());
}

由于此堆的开销相当大，因此实际上不如基于 dynamic-array 的堆快。

Answer 2

正如@trincot 之前回答的那样，一种方法是构建一个链接结构，其节点具有指向其他节点的 left、right、parent 指针。此实现将插入 O(logn) 时间（因为堆是 almost complete binary tree）。但实际上，它会相当低效，因为它需要为每个节点维护许多（至少 3 个）指针（也就是每个项目至少 3 * 8 = 24 字节的内存开销）。

话虽如此，可以省略 prev、next 指针（降低每项的内存开销），因为我们可以轻松计算它们（也在 O(logn) 时间内）。

例如，next 将是（prev 类似）：

Node next(Node t)
{
    if (t == null)
       return null;
    if (t.parent == null)
       return t.left; // climb down one level (see @trincot's comment) 
    // if left child, next is my right sibling
    if (t == t.parent.left)
       return t.parent.right;
    // so, i am right child of my parent
    Node p = next(t.parent);
    if (p != null) {
       return p.left;
    } else {
       return null; // no next exists
    } 
}

插入 O(log n) 的动态堆实现

Dynamic heap implementation with insert O(log n)

java

arraylist

time-complexity

heap