ADT

• insert(value)
• remove()
• isEmpty()

Where value is among int, string, double, char... or objects that supports < operator.

Heap

Unsorted Array: O(1)* insert, O(n) removeMin (need to find min first)

Unsorted Linked List: O(1) insert, O(n) removeMin

Sorted Array: O(n)* insert, O(1) removeMin

Sorted Linked List: O(n) insert, O(1) removeMin

It's easier to removeMin on sorted structures and insert on unsorted structures.

To balance the worst case time to O(lg(n)) insert and O(lg(n)) removeMin, we could use a binary tree.

Definition

(min-)Heap

A complete binary tree t is a min-heap if:

• T = {} or
• T = {r, T_L, T_R} where r is less than roots of {T_L , T_R} and {T_L , T_R} are min-heaps.

Logically it's a tree, and implementation-wise, it's an array.

The heap above in array would be: [1, 4, 5, 12, 7, 6, 8, 13, 14, null, null, 11, null, null, null]

We could define left must be larger or smaller than right, but as long as all roots are smaller than their children, it's a min-heap.

Priority queues are based on heaps.

Operations

• Left child of node[i]: node[2*i]
• Right child of node[i]: node[2*i + 1]
• Parent of node[i]: floor(i/2)

We could also store the number of nodes, n, in node[0], and the above remains the same. Knowing the number of nodes can help you know where in the array is outside of the heap.

How to Insert

template <class T>
void Heap<T>::_insert(const T & key) {
    // check if there's enough space
    if (size_ == capacity) {
        _growArray();
    }
    
    // insert element at the end of array
    item_[++size] = key;
    
    // restore heap property
    _heapifyUp();
}

template <class T>
void Heap<T>::_heapifyUp(size_t index) {
    if(index>1) { // 1 is the root here, as we stored size in 0
        if(item_[index] < item_[parent(index)]) {
            std::swap(item_[index], item_[parent(index));
            _heapifyUp(parent(index));
        }
    }
}

How to Remove

removeMin() is removing root of a min-heap, and removeMax() is removing root of a max-heap.

When removing root:

1. Swap root with the last node.
2. Remove the last node (root).
3. Heapify to restore heap property

template <class T>
T Heap<T>::_remove() {
    T min_value = item_[1];
    item_[1] = item_[size--]; // swap with last and delete
    
    _heapifyDown();
    return min_value; // return original root value
}

template <class T>
void Heap<T>::_heapifyDown(size_t index=1) {
    if(!_isLeaf(index)) {
        size_t minChildIndex = _minChild(index);
        if(item_[index] > item_[minChildIndex]) {
            std::swap(item_[index], item_[minChildIndex]);
            _heapifyDown(minChildIndex);
        }
    }
}

How to Build a Heap

buildHeap - heapifyUp: O(n*log(n))  – each insert is O(log(n))

void Heap<T>::buildHeap() {
    for(unsigned i=2; i<= size_; i++) {
        heapifyUp(i);
        // takes O(n logn)
    }
}

buildHeap - heapifyDown: O(n)  – takes time of O(sum of the height of all sub trees)

void Heap<T>::buildHeap() {
    for(unsigned i=parent(size_); i>0; i--) {
        heapifyDown(i);
        // takes O(n)
    }
}

Prove heap building running time:

• S(h): Sum of heights of all nodes in a complete tree of h
• S(0) = 0
• S(1) = 1 + 0 + 0 = 1
• S(2) = 2 + 1 + 1 = 4
• ....
• S(h) = h + 2 * S(h-1) = 2^(h+1) -h - 2
• Since h<=lg(n),
• O(2^(lg(n)+1) - lg(n) -2) = O(n-2-lg(n)) = O(n)