Heap (priority queue)

A type of tree that maintain a weak ordering

Fill in each node from left to right and maintain the heap property (weak ordering to max or min)

Addition

Add new node to the very bottom and then bubble up (by swapping above) until the heap property is restored

Deletion

Remove the node, swap the lowest node in it's place and heapify down

Min Heap

Top node is the smallest

20
|   |
30   100
| |  |  |
31 80 3000 1001

Max Heap

Top node is the largest

ArrayList Representation

It can be helpful to represent heaps in an array list so accessing elements at the end is easier.

[0, 1, 2, 3, 4, 5, 6, 7, 8]

Children can be found with this function:

2i + 1 === left child
2i + 2 === right child

And a nodes parent can be found with:

Math.floor((i - 1)/2)

Insert and delete operations have a worst case runtime of O(logn) because the depth of the tree will always be logn

Implementation (Min Heap)

class MinHeap {
    public length: number;
    private data: number[];

    constructor() {
        this.data = [];
        this.length = 0;
    }

    insert(value: number): void {
        this.data[this.length] = value;
        this.heapifyUp(this.length);

        this.length++;
    }

    delete(): number | undefined {
        if (this.length <= 0) return undefined;

        const out = this.data[0];
        this.length--;

        if (this.length === 0) {
            this.data = [];
            return out;
        }

        this.data[0] = this.data[this.length];
        this.heapifyDown(0);
        return out;
    }

    private heapifyUp(idx: number): void {
        if (idx === 0) return;

        const val = thid.data[idx];

        const pidx = this.parent(idx);
        const pval = this.data[pidx];

        if (pval > val) {
            // swap
            this.data[idx] = pval;
            this.data[pidx] = val;

            this.heapifyUp(pidx);
        }
    }

    private heapifyDown(idx: number): void {
        const lidx = this.leftChild(idx);
        const ridx = this.rightChild(idx);

        if (idx >= this.length || lidx >= this.length) return;

        const lval = this.data[lidx];
        const rval = this.data[ridx];
        const val = this.data[idx];

        if (lval > rval && val > rval) {
            this.data[idx] = rval;
            this.data[ridx] = val;

            this.heapifyDown(ridx);
        } else if (rval > lval && val > lval) {
            this.data[idx] = lval;
            this.data[lidx] = val;

            this.heapifyDown(lidx);
        }
    }

    private parent(idx: number): number {
        return Math.floor((idx - 1) / 2);
    }

    private leftChild(idx: number): number {
        return idx * 2 + 1;
    }

    private rightChild(idx: number): number {
        return idx * 2 + 2;
    }
}