Sunday, September 4, 2016

Algorithms - Heaps



Heaps – Heap is a form of binary tree. Its underlying data structure can be a list with children nodes in 2k+1 and 2k+2 position It could be a max-heap or min-heap.
A max-heap is kind of heap with top node (root node) having the maximum value. At any index i, a max-heap would have element[i] greater than its children.

Heap (minheap) provide optimal time for all three – insert, findminimum, deleteminimum.
The children index (2i and 2i + 1) can found very easily as multiplying by 2 is nothing BUT LEFT SHIFT. Parent on the other hand(i/2) can be found using RIGHT SHIFT.

Priority queues are implemented using heaps. (min-heap).

MAX-HEAPIFY – This operation when done on a list A in position i i.e MAX-HEAPIFY(A,i) brings the ith element “downwards” (if it is smaller), so the subtree rooted at i obeys MAX HEAP PROPERTY.

Implementation of MAX-HEAPIFY in Python –
def max_heapify(A, i):   
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    if left < len(A) and A[left] > A[largest]:
        largest = left
    if right < len(A) and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

The complexity of MAX-HEAPIFY is O(logn).

To build a MAX-HEAP, you run MAX-HEAPIFY on the lower nodes (having children) UPTO to the top node. There is no point in running MAX-HEAPIFY on bottommost children nodes.
So for array of size n, you run MAX-HEAPIFY from floor(n/2) till the top node (i.e n=0). Below is the implementation –

def buildmaxheap(list):
    i=int(len(list)/2)
    while (i>=0):
        max_heapify(list,i)
        i=i-1

The above is the fundamental step of heapsort.

Following steps are done in heapsort –
1)      Build max-heap (A)
2)      From last element to i=1, loop
3)      Exchange current element with A[0] //top most element.
4)      Reduce heap-size, so that the last element is disconnected.
5)      Run MAX-HEAPIFY(A,0)
Below is the implementation –
i = len(list)
list2 = []
while (i>0):
    list[i-1],list[0] = list[0],list[i-1]
    list2.append(list.pop())
    max_heapify(list,0)
    i = i-1

The complexity of heapsort is O(nlogn) as we running MAX-HEAPIFY O(logn)  (n-1) times.