Heap Sort

Heap is an implementation of Priority Queue data structure

There are two kinds of Heaps: Max Heap and Min Heap.
In Max Heap, every element is greater than its left and right children
In Min Heap, every element is less than its left and right children.

An array should be visualized as a Tree structure, when working with heaps.

Heap properties:
1. Each element is greater(max heap) or less (min heap) than its left and right children
2. The tree should be a complete binary tree

Complete Binary tree:
Each node should have at most two children, except leaf nodes.
If a node has right child, then it must have left child.
If a node has no left/right child, then all the next nodes in that level and in next level should not have any children.

Typical operations performed on an Heap:
1. Get parent element index
2. Get Left Child index
3. Get right child index
4. insert an element
5. delete the highest priority element
6. percolate down: Its an operation to satisfy the heap property from the given index down to all its child nodes.
7. Heapify: Given an array, which is not satisfying heap properties, make it as a heap.

Code:
import java.util.Arrays;

class Heap {
        private int array[] = new int[10];
        private int capacity = 0;
        private int count = 0;

        Heap() {}

        //Parent of element is located exactly at (i-1)/2 position
        public int getParent(int index) {
                if(index == 0)
                        return -1;
                else
                        return (index-1)/2;
        }

        //left child is located at 2*i+1 position
        public int getLeftChild(int index) {
                int left = 2 * index + 1;

                if(left > count-1)
                        return -1;
                else
                        return left;
        }

        //right child is located at 2*i+2 position
        public int getRightChild(int index) {
                int right = 2 * index + 2;

                if(right > count-1)
                        return -1;
                else
                        return right;
        }

        //gives the size of the heap
        public int getSize() {
                return this.count;
        }

        //Given an array, which is not satisfying the heap properties, 

        //this method makes the array as an heap structure

        //One important observation is that, all leaf nodes, by default satisfy the heap property

        //since they do not have any children, so not required to compare them with any one

        //so starting from (len-1)/2 index till root element, percolate down

        public void buildHeap(int[] in) {

                this.array = in;

                int len = in.length;

                this.count = len;

                for(int i=(len-1)/2; i>=0; i--)

                        percolateDown(i);

        }

        //this inserts the element one by one from the given array into heap

        //then deletes the max element from heap and keeps it back in the input array

        public void heapSort(int[] in) {

                for(int i=0; i<in.length; i++)

                        insert(in[i]);

                for(int i=0; i<in.length; i++)

                        in[i] = deleteMax();

                System.out.println(Arrays.toString(in));

        }

        //insert the element at end

        //then compare it with its parent and if the parent is less than the inserted element

        //swap the current element with its parent

        //now repeat this procedure from parent, till we reach the root element

        public void insert(int data) {

                array[count++] = data;

                if(count == 1)

                        return;

                int parent = (count-2)/2;

                int currPos = count-1;

                while(array[parent] < array[currPos]) {

                        int temp = array[parent];

                        array[parent] = array[currPos];

                        array[currPos] = temp;

                        currPos = parent;

                        parent = getParent(parent);

                }

        }

        //We need to make the array satisfy the heap property at each level

        //Given an index, check the max element index by comparing this with its left and right children

        //now swap the current index element with the max(either left/right) element

        //then repeat this procedure from the max(left/right) position till we reach leaf nodes

        public void percolateDown(int i) {

                int left = -1, right = -1;

                left = getLeftChild(i);

                right = getRightChild(i);

                int max = i;

                //compare the left and right children with current element

                //determine the max element position

                //and exchange it with current element position

                if(left != -1 && array[left] > array[max])

                        max = left;

                if(right != -1 && array[right] > array[max])

                        max = right;

                if(max != i) {

                        //exchange max and i index elements

                        int temp = array[i];

                        array[i] = array[max];

                        array[max] = temp;

                        //since at this position heap property violated

                        //Follow top-down from this element as well

                        percolateDown(max);

                }

        }

        //Deletes the highest priority element(which is at index 0)

        //To delete the max element, swap root with last element

        //now decrease the count by 1

        //percolate down from the root, to make the array satisfy the heap properties

        public int deleteMax() {

                if(count == 0)

                        return -1;

                int deletedEle = array[0];

                System.out.println("Deleting: " + deletedEle);

                if(count == 1) {

                        --count;

                        return deletedEle;

                }

                array[0] = array[--count];

                percolateDown(0);

                return deletedEle;

        }

        static public void main(String[] args) {

                int[] ar = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};

                System.out.println(Arrays.toString(ar));

                new Heap().heapSort(ar);

        }

}

eg:

Complexity Analysis: