Heap Sort

Heap sort is the one of the most efficient comparison-based algorithms. A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap.
A heap is a binary tree that has special structure compared to a general binary tree:

The root is greater than any value in a sub-tree

this means the highest priority is at the root
this is less information than a BST (Binary Search Tree) and this is why it can be easier and faster

2. It is a complete tree

the height is always log(n) so all operations are O(log(n))

Balanced binary trees:
Recall:

The depth of a node is its distance from the root
The depth of a tree is the depth of the deepest node

A binary tree of depth n is balanced if all the nodes at depths 0 through n-2 have two children

Left-justified binary trees:
A balanced binary tree of depth n is left-justified if:

it has 2n nodes at depth n (the tree is “full”), or
it has 2k nodes at depth k, for all k < n, and all the leaves at depth n are as far left as possible

Plan of attack:

First, we will learn how to turn a binary tree into a heap
Next, we will learn how to turn a binary tree back into a heap after it has been changed in a certain way

Code:

import java.util.*;

/**
 *
 * @author Manoj
 */

public class HeapSort {

public static int heapSize;
    public static int LEFT(int i)
    {
        //returns left index of a zero index based array
        return 2*i+1;
    }

public static int RIGHT(int i)
    {
        //returns right index of a zero based array
        return 2*i+2;
    }

public static void BUILD_MAX_HEAP(int A[])
    {
        heapSize = A.length;//heap size initialised
        for(int i=A.length/2; i>=0;i--) //since n/2, n/2+1 ... are leaves we can start from n/2 step downwards
        {
            //call MAX_HEAPIFY on each root node starting from n/2
            MAX_HEAPIFY(A, i);
        }
    }

public static void MAX_HEAPIFY(int A[],int i)
    {
        int l=LEFT(i);//the left element's index which is 2*i+1 (for zero based indexed array)
        int r=RIGHT(i);//right index = 2*i+2;
        int largestElementIndex = -1;//index can't be negative so initialise largest index , it will be used later
        //heapSize is the current size of the heap being worked upon
        //check if left index lies within the heap.
        //if element at left index is greater than root(A[i]) element, max heap property is violated
        //copy the index of violated element in largestElementIndex
        if(l<heapsize && A[l]>A[i]){
            largestElementIndex = l;
        }
        else //if max heap property is not violated copy the root's index in largestElementIndex
        {
            largestElementIndex=i;
        }
        //check to see the right sub tree for max heap property violation
        //here the largestElementIndex is calculated from previous step
        if(r<heapsize && A[r]>A[largestElementIndex])
        {
            largestElementIndex = r;
        }
        //if root doesn't has the largest index then swap the largest element with root element

if(largestElementIndex!=i)
        {
            int temp = A[i];
            A[i]=A[largestElementIndex];
            A[largestElementIndex]=temp;
            //after swap, recursively call the MAX_HEAPIFY on the largest index(root element)
            MAX_HEAPIFY(A, largestElementIndex);
        }
    }

public static void HEAP_SORT(int A[])
    {
        //max heap is built with heapSize initialised
        BUILD_MAX_HEAP(A);
        //starting from end loop through entire array
        for(int i=A.length-1;i>=0;i--)
        {
            //since heap is already heapified and maintains max heap property
            //the first element of the array is root of max heap
            //swap it with the extreme element of the array i.e. setting the largest element to the end of array
            int temp = A[0];
            A[0]=A[i];
            A[i]=temp;
            //reduce the heap window by 1
            heapSize  = heapSize-1;
            //call max heapify on the reduced heap
            MAX_HEAPIFY(A,0);
        }
    }

public static void main(String[] args) {

int A[] = new int[]{16,11,15,9,10,13,14,8,2,1,5,12,6,3,7,4};
 System.out.println("Before: " + Arrays.toString(A));
        HEAP_SORT(A);
        System.out.println("After:  " + Arrays.toString(A));
    }
}

Output:

Subscribe to: Posts ( Atom )

Heap Sort

OUR TECH-PROJECTS

DOWNLOAD ANY ONLINE VIDEOS

LABELS

Development Accessories

POPULAR POSTS