Heap

About

It is a Binary Tree where every child is:

• Smaller than the current node. (Max Heap)

• Larger than the current node. (Min Heap)

Heap has a weak ordering, meaning that it is not totally ordered like a BST.

The order is only locally maintained, enough to satisfy the Heap conditions above.

Heap is usually a Heap or Heap.

Whenever a node is added or deleted, the Tree MUST be ajusted.

Used in priority queues for example.

Node sequence of Heap

Nodes of the Heap follow a sequence to defines the first and last node of the Tree.

This sequence also helps on insertion and deletion, since inserted elements are added to the end (or last position), and deleted elements are deleted at position 0 (first position).

Inserting an element (Tree)

1. Elements are added at either:

   • The last level (height) where you have an empty space. (Usually from left to right)

   • New created level. (Usually from left to right)

2. Then check the added element $X$ against $Ancestor_X$ to see if it satisfy Heap conditions.

3. Repeat 2. until Heap conditions are satisfied.

The repeat 2. process is called Heapify Up, where the added node thies to bubble up in the Tree.

Runs on $O(log N )$ since the Tree is always balanced.

Deleting an element (Tree)

1. The top element is the one deleted.

2. Then the very last node $X$ in the Tree takes the place of the top node.

3. The $X$ node is checked against:

   1. In a MinHeap, the smallest of $X_{child}$, then if $X_{child} < X$ they swapp positions.

   2. In a MaxHeap, the highest of $X_{child}$, then if they swapp positions.

4. Repeat 3. until Heap conditions are satisfied.

The repeat 3. process is called Heapify Down, where the node that took place of the deleted node tries to bubble down in the Tree.

Runs on $O(log N )$ since the Tree is always balanced.

Implementing Heap with Arrays

Heaps can easily be implemented with Arrays Data Structures, and thus facilitating the removal of nodes.

You simulate left and right childs and parent nodes in Arrays with the following formulas: (where i is the current node index being looked)

• left child: $2i + 1$

• right child: $2i + 2$

• parent node: $\lfloor\frac{(i-1)}{2}\rfloor$

class MinHeap<T> {
    length: number = 0;
    #data: T[] = [];
    
    insert(value: T): void {
        this.data[this.length] = value;
        this.heapifyUp(this.length);
        this.length++;
    }
    
    delete(): T | undefined {
        if (this.length === 0) return undefined;
        if (this.length === 1) {
            this.length--;
            return this.data.pop();
        }
        const removed = this.data[0];
        this.data[0] = this.data[this.length - 1];
        delete this.data[this.length - 1];
        this.length--;
        this.heapifyDown(0);
        return removed;
    }
    
    private heapifyUp(i: number): void {
        if (i === 0) return;
        
        const parentI = this.parent(i);
        const parentValue = this.data[parentI];
        const currValue = this.data[i];
        
        // Since it is MinHeap we bubble up the value if currValue is smaller
        if (parentValue > currValue) {
            this.data[i] = parentValue;
            this.data[parentI] = currValue;
            this.heapifyUp(parentI);
        }
    }
    private heapifyDown(i: number): void {
        if (i >= this.length) return;
        
        const currLeftI = this.leftChild(i);
        const currRightI = this.rightChild(i);
        if (currLeftI >= this.length) return;
        
        const currLeftValue = this.data[currLeftI];
        const currRightValue = this.data[currRightI];
        const currValue = this.data[i];
        
        // Right node is the smallest child
        if (currLeftValue > currRightValue && currValue > currRightValue) {
            this.data[i] = currRightValue;
            this.data[currRightI] = currValue;
            this.heapifyDown(currRightI);
        }
        // Left node is the smallest child
        else if (currRightValue > currLeftValue && currValue > currLeftValue) {
            this.data[i] = currLeftValue;
            this.data[currLeftI] = currValue;
            this.heapifyDown(currLeftI);
        }
    }
    
    private parent(i: number): number {
        return Math.floor((i - 1) / 2);
    }
    private leftChild(i: number): number {
        return i * 2 + 1;
    }
    private rightChild(i: number): number {
        return i * 2 + 2;
    }
}