CC-10 : Implement Heap Sort Algorithm.

Description:

Heap Sort uses Binary Heap structure to sort the input array. In the first step, the input array is converted into Binary Heap, such that every parent node is greater than the child nodes. Then to sort the elements, the largest element of heap is swapped with last element of the heap. Now the largest element is at its correct position at the end of the array. The heap size is reduced by 1 and the remaining heap elements are heapified once again. Now again we can move the largest element of heap to second largest position of the array and so on till all the elements are sorted. Given an input array, sort its elements using Heap Sort.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Sorted Array: 1, 3, 4, 20, 33, 62, 97, 122, 124,

Pseudocode:

sort(nums[]):

Integer array named nums is received as input parameter.

Set variable len to nums.length.

To convert input array to Binary Max Heap : Iterate through nums using for loop with idx as iteration variable and values of idx ranging from len/2-1 to 1 where idx is decremented by 1 after each iteration:

Call updateHeap(nums, len, idx).

To sort the elements of Binary Max Heap: Iterate through nums using for loop with idx as iteration variable and values of idx ranging from len-1 to 1 where idx is decremented by 1 after each iteration:

Swap nums[0] and nums[idx].

Call updateHeap(nums, idx, 0).

Return int array return by call to megrSort(leftArrRet, rightArrRet).

UpdateHeap(nums, len, idx) (also known as Heapify() method):

This method takes nums array, length of inpur array to be processed and index idx of heap elements to be processed as input variable.

It moves the node data at index idx to its correct position in the Max Heap.

If node data at left child index of idx or right child index of idx is greater than node data at index idx:

Node data at index idx and its child index childIdx with greater node data is swapped.

UpdateHeap() is recursively called with the index of the child childIdx .

Code:

public int[] sort(int nums[]) {
	int len=nums.length;
	for (int idx=len/2-1; idx>=0; idx--) {
		updateHeap(nums, len, idx);
	}
	for (int idx=len-1;idx>0; idx-- ){
		int temp=nums[0];
		nums[0]=nums[idx];
		nums[idx]=temp;
		updateHeap(nums, idx,0);
	}	
	return nums;
}

public void updateHeap(int[]nums, int len, int idx) {
	int parentIdx=idx;
	int leftChildIdx= 2*idx+1;
	int rightChildIdx=2*idx+2;
	if ((leftChildIdx < len) && (nums[leftChildIdx] > nums [parentIdx])) {
		parentIdx=leftChildIdx;
	}
	if ((rightChildIdx < len) && (nums[rightChildIdx] > nums [parentIdx])) {
		parentIdx=rightChildIdx;
	}
	if (parentIdx != idx) {
		int temp=nums[idx];
		nums[idx]=nums[parentIdx];
		nums[parentIdx]=temp;
		updateHeap(nums, len, parentIdx);
	}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SortHeapSort {
 	
public int[] sort(int nums[]) {
	int len=nums.length;
	for (int idx=len/2-1; idx>=0; idx--) {
		updateHeap(nums, len, idx);
	}
	for (int idx=len-1;idx>0; idx-- ){
		int temp=nums[0];
		nums[0]=nums[idx];
		nums[idx]=temp;
		updateHeap(nums, idx,0);
	}	
	return nums;
}

public void updateHeap(int[]nums, int len, int idx) {
	int parentIdx=idx;
	int leftChildIdx= 2*idx+1;
	int rightChildIdx=2*idx+2;
	if ((leftChildIdx < len) && (nums[leftChildIdx] > nums [parentIdx])) {
		parentIdx=leftChildIdx;
	}
	if ((rightChildIdx < len) && (nums[rightChildIdx] > nums [parentIdx])) {
		parentIdx=rightChildIdx;
	}
	if (parentIdx != idx) {
		int temp=nums[idx];
		nums[idx]=nums[parentIdx];
		nums[parentIdx]=temp;
		updateHeap(nums, len, parentIdx);
	}
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	SortHeapSort sort=new SortHeapSort();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	System.out.println("\nSorted Array:");
	retVal=sort.sort(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}