Binary Heaps

Min-heaps

The root node is always the min value
The tree must be a complete tree.
the only relationship between the subtrees is that they are both greater than their parent node. There is no other relationship between them.

Implementations

complete binary tree
leftist heap
skew heap

We will use complete binary tree to implement heaps.

In complete binary trees, new elements are inserted in breadth-first-traversal.
Array storage: a complete tree can be easily stored as an array.
- leave the first element of array empty $\rightarrow$ helps with the mathematical forumation of parent-child relations
- parent of node at position $k$ is $\displaystyle \lfloor \frac{k}{2} \rfloor$
- children of a node at position $k$ are indexed at $2k$ and $2k+1$

Operations

push():
- insert the new element at the first empty position of array ($pos_new$)
- compare the new element with its parent node at $\lfloor \frac{pos_new}{2} \rfloor$
- Swap them if $\text{parent } < \text{ new element}$, recursively and continue this check until the root
- This is called percolation up
- Running time: $\Theta(\ln(n))$
pop():
- Retrieve the root element
- Copy the last element to the root
- Compare the new root with its children, and swap them if necessary
- Repeat the above until reaching a leaf node
- This is called percolation down
- worst case $\Theta(\ln (n))$
top()
- retrieve the root, no change to the tree
- Running time: $\Theta(1)$

Implementing min-heap using an array

parent of node $k$ is $k/2$
children of node $k$ are indexed by $2k$ and $2k+1$

#include <vector>

template<typename Type>
class BinaryHeap {
    private:
        int current_size;
        vector<Type> array;
        void buildHeap();
        void percolateDown(int);

    public:
        explicit BinaryHeap(int);
        explicit BinaryHeap(const vector<Type> &);
        bool isempty() const;
        const Type & min() const;
        void makeEmpty();
        void insert(const Type &);
}

Constructors

template<typename Type>
BinaryHeap<Type>::BinaryHeap(int capacity = 100) 
                 : array(capaity +1 ), current_size{0} {
                 // empty
}

template<typename Type>
BinaryHeap<Type>::BinaryHeap(const vector<Type> & items) 
                 : array(items.size() + 10 ),
                   current_size{items.size()} {
    for (int i=0; i<items.size(); ++i) 
        array[i + 1] = items[i];

    buildHeap();
}

isempty()

template<typename Type>
bool BinaryHeap<Type>::isempty() const {
    return (current_size == 0);
}

min()

template<typename Type>
Type BinaryHeap<Type>::min() const {
    if (current_size == 0) 
        throw UndeflowExeption;

    return array[1];
}

makeEmpty()

template<typename Type>
void BinaryHeap<Type>::makeEmpty() {
    current_size = 0;
}

buildHeap()

template<typename Type>
void BinaryHeap<Type>::buildHeap() {
    for (int i = current_size / 2; i > 0; --i)
        percolateDown(i);
}

percolateDown()

template<typename Type>
void BinaryHeap<Type>::percolateDown(int pos) {
    int child_idx;
    Type tmp = std::move(array[pos]);

    for( ; pos * 2 <= current_size; pos = child_idx) {
        child_idx = pos * 2;

        if (child_idx != current_size && 
            array[child_idx + 1] < array[child_idx] ) 
            ++ child_idx;

        if (array[child_idx] < tmp) 
            array[pos] = std::move(child_idx);
        else    
            break;
    }

    array[pos] = std::move(tmp);
}

deleteMin()

template<typename Type>
void BinaryHeap<Type>::deleteMin() {
    if (isempty()) {
        throw UnderflowException;
    }

    array[1] = std::move( array[current_size --] );
    percolateDown( 1 );
}

Comparison

	Multiple (m) Queues	AVL (balanced) tree	Binary Heap
top	$O(m)$	$\Theta(\ln(n))$	$\Theta(1)$
push	$\Theta(1)$	$\Theta(\ln(n))$	$\Theta(1)$ on average
pop	$O(m)$	$\Theta(\ln(n))$	$O(\ln(n))$

For bunary heap, inserting/accessing/deleting an element at different locations:

	front of the tree	arbitray location	back of the array
insert	$O(\ln(n))$	$O(1)$	$O(1)$
access	$O(1)$	$O(n)$	$O(n)$
delete	$O(\ln(n))$	$O(n)$	$O(n)$

Other heaps

Leftist heap
Skew heap
Binomial heap
Fibonacci heap



In [ ]: