HEAP:

Insertion, deleting the minimum and finding the minimum takes different time in different data structures.
For an unsorted array: Insertion - O(2) , Finding Min - O(n), Deleting Min - O(n)

For an unsorted Linked List: Insertion - O(1) , Finding Min - O(n) , Deleting Min - O(n)

For a sorted array: Insertion - O(n) , Finding Min - O(1) , Deleting Min - O(n)

In order to optimise these three functions, we use Heaps.

For a Heap: Insertion - O(logn) , Finding Min - O(1) , Deleting Min - O(logn)

Representation:

Heap is an almost complete binary tree but is represented using array data structure. Its basically storing a tree in an array.

For a tree:

100

/ \

10 20

/ /

1 4 3

Array would be : [100,10,20,1,4,3]

For any node at index i :

Parent(i) = i/2

Left Child(i) = 2*i

Right Child(i) = (2*i)+1

• If the array is in ascending order, its a min heap. If array is descending, its a max heap.
• There can be more than one max/min heaps for a particular array.

If you want to find the elements that will be the leaves of the tree then the ones who's index is between (n/2)+1 and n both inclusive will be the leaves of the tree (THIS IS THEORETICAL CONSIDERING THE INDEX OF THE LIST STARTS FROM 1)

AS THE INDEX OF THE LIST START FROM 0, leaves will be between n/2 and n-1 both inclusive.

BUILDING HEAP:

Working is as follows:

• Start from the highest index that is not a leaf node. Then check who's the left and right child of that node.
• If they left child exists, check whether its greater than the current node, if it is then LARGEST = LEFT CHILD else LARGEST = CURRENT NODE
• If right child exists, check whether its greater than the LARGEST, if it is then LARGEST = RIGHT CHILD
• Now if LARGEST != CURRENT NODE, swap them and run MAX_HEAPIFY on largest.

-------------------------------------------< NOTE >-------------------------------------------------------

Above mentioned process is how the heap works, but due to lists starting with 0 in python, we cannot just calculate left child as 2*index etc because for the root node i.e index 0 the left child will be 0(2*0) so I have modified a process a little bit. JUST SO TO MAINTAIN THE INDEX I have set left_child to (2*i) +1 and also I have set a special case for the root node. If confused watch this : https://www.youtube.com/watch?v=2fA1FdxNqiE

-------------------------------------------< NOTE >-------------------------------------------------------

MAX HEAPIFY:

def max_heapify(A,i):
    if i == 0:
        left_child = 1
        right_child = 2

    else:
        left_child = (2*i)+1
        right_child = left_child+1

    if left_child<len(A) and A[left_child]>A[i]:
        largest = left_child
    else:
        largest = i

    if right_child<len(A) and A[right_child]>A[largest]:
        largest = right_child

    if largest!=i:
        (A[largest],A[i]) = (A[i],A[largest])
        max_heapify(A,largest)

def build_max_heap(A):
    for i in range((len(A)/2)-1,-1,-1):
        max_heapify(A,i)

a = map(int,raw_input().split())
build_max_heap(a)

EXTRACT MAX :

This can be done as follows:

• In a max heap, maximum element will be the first element so store the first element in a variable called MAX.
• Now remove the last element from the heap and make it the root node and perform heapify on it

def extract_max(A):
    max = A[0]
    last = A.pop()
    A[0] = last
    max_heapify(A,0)
    return max

INCREASE KEY :

def increase_key(A,i,key):
    A[i] = key
    while i!=0 and A[i] > A[i/2]:
        (A[i],A[i/2]) = (A[i/2],A[i])
        i = i/2

MIN HEAPIFY:

def min_heapify(A,i):
    if i == 0:
        left_child = 1
        right_child = 2
    else:
        left_child = (2*i)+1
        right_child = left_child+1

    if left_child<len(A) and A[left_child]<A[i]:
        smallest = left_child
    else:
        smallest = i

    if right_child<len(A) and A[right_child]<A[largest]:
        smallest = right_child
    if smallest!=i:
        (A[smallest],A[i]) = (A[i],A[smallest])
        min_heapify(A,smallest)