Binary Heap

Properties

A binary heap is a binary tree with following properties.

It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible)
A binary heap is either min heap or max heap. In a min binary heap, the key at root must be minimum among all keys present. The same property must be recursively true for all nodes.

Data Structure Representation

It is typically represented as array.

The root element will be at Arr[0]. 
Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[i/2]     Returns the parent node
Arr[(2*i)+1] Returns the left child node
Arr[(2*i)+2] Returns the right child node

Insert

When we insert into a min-heap, we always start by inserting the element at the bottom. We insert at the right most spot so as to maintain the complete tree property.

Then we fix the tree by swapping the new elements with its parent, until we find an appropriate spot for the element.

This algorithm will also take O(logN) time.

Extract Min or Max Element

First, we remove the min element and swap it with the last element in the heap. Then we bubble down this element, swapping it with one of its children until heap property is restored.

This algorithm will also take O(logN) time.

Heapify

void heapify(vector<int> &arr, int n, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // If left child is larger than root
    if (left < n && arr[left] < arr[smallest]) {
        smallest = left;
    }

    // If right child is larger than largest so far
    if (right < n && arr[right] < arr[smallest]) {
        smallest = right;
    }

    // If largest is not root
    if (smallest != i) {
        swap(arr[i], arr[smallest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, smallest);
    }
}

Build Heap

Binary Heap supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Time complexity for Building a Binary Heap is O(n).

BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Heap