Heap Sort Algorithm

What is heap?

A heap is defined as a complete binary tree with n nodes such that

1. Value of each node is less than or equal to the root. When root of the binary tree is the biggest number in the heap. This type of heap is known as max Heap  or descending Heap.


2. Value of each node is greater than or equal to the root. When root of the binary tree is the smallest number in the heap. This type of heap is known as min Heap  or ascending Heap.

Each node in the heap corresponds to an element of the array, with the root node corresponding to the element with index 0 in the array. Considering a node corresponding to index i, then its left child has index (2*i + 1) and its right child has index (2*i + 2).

Heap can be used to sort the data in ascending and descending order. The method is known as Heap Sort. Heap Sort involves two basic step

1. Build Heap

•      Create max heap to sort the data in ascending order
•      Create min Heap to sort data in descending order

2. Heapify


ALGORITHM 
    Heapify(A, i){
        l <- left(i)
        r <- right(i)
        if l <= heapsize[A] and A[l] > A[i]
            then largest <- l
            else largest <- i
        if r <= heapsize[A] and A[r] > A[largest]
            then largest <- r
        if largest != i
            then swap A[i] <-> A[largest]
                Heapify(A, largest)
    }

    Buildheap(A){
        heapsize[A] <- length[A]
        for i <- |length[A]/2| downto 1
            do Heapify(A, i)
    }

    Heapsort(A){
        Buildheap(A)
        for i <- length[A] downto 2
            do swap A[1] <-> A[i]
            heapsize[A] <- heapsize[A] - 1
            Heapify(A, 1)
    }