Dynamic heap implementation with insert O(log n)

Question

I'm trying to implement a Min Heap in Java, but between studying the complexity and the actual implementation, I realized that it is not clear to me how O (log n) insertion into the heap can be if a dynamic array (such as ArrayList) is used as the base structure.

I understand properly that insert operation in a Heap is O(log n) because we add new item at the end of the array, and we swap each item with his parent, up to a maximum of log n swaps.

But this theorically will works only if you have a base structure big enough to can insert new element: if we need to grow array, operation will take O(n). I know that add element in ArrayList has amortized O(1), but i want to know if is possible to implement the heap by accomplishing with real O(log n) insert operation.

I can use linkedList to accomplish O(1) in insert, but this means that other heap operations (like delete) will no longer have O(log n) complexity.

I also can use a fixed array, but this doesn't allow to insert in heap many elements as you want.

Is there another way? Thanks to all

Answer 1

You can implement a heap with nodes that are both part of a doubly linked list, and part of a threaded binary tree.

The heap maintains a reference to the root (head) and tail node.

So we can imagine a node having 5 pointers: prev, next, left, right, parent. However, we don't need to store right as -- when it exists -- it is equal to left.next.

Then the basic operations are as follows:

• Extract min:

  • Remember the value of the root
  • Get the last node (tail), copy its value to the root, and remove the node.
  • Perform the sift down operation to restore the heap property.
  • Return the value from the first step

• Add

  • Create a node with the given value and insert it as last node (and last child), so it becomes tail.
  • Perform the bubble up operation to restore the heap property.

Here is an implementation in 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();
    }

Here is the same as a runnable JavaScript snippet:

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());
}

As the overhead of this heap is considerable, it is in practice not as fast as a dynamic-array based heap.

Answer 2

As @trincot answered before, a way to go is to build a linked struct with nodes having left, right, parent pointers to other nodes. This implementation will have an insertion of O(logn) time (because the heap is an almost complete binary tree). In practical terms, though, it would be rather inefficient as it would require to maintain many (at least 3) pointers per node (aka, a memory overhead of at least 3 * 8 = 24 bytes per item).

Having said that, one can omit the prev, next pointers (lowering the memory overhead per item) because we can easily compute them (in O(logn) time also).

For example, next would be (prev is similar):

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
    } 
}