Heapsort is a sorting algorithm based on a Binary Heap data structure. It’s a comparison-based sorting similar to Selection Sort where first find maximum item and place that maximum item at the end. Repeat the same steps for remaining items until all items sorted.

Points to Remember

• Data structure: Array
• Worst-case performance: O(n\log n)
• Best-case performance : O(n\log n) (distinct keys) O(n) (equal keys)
• Average performance: O(n\log n)
• Worst-case space complexity: O(n) total O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

• Heapsort is a more favorable in worst-case O(n log n) runtime.

Disadvantage

• Heapsort slower in practice on most machines than a well-implemented quicksort.
• Heapsort is not a stable sort but in-place algorithm.

Binary Heap Data Structure

Binary Heap is a type of Complete Binary Tree where items stored such a way like a parent node value is greater than the values of its child nodes. That is also called as Max heap. it can be represented in the form of a binary tree or array.

Binary Tree Representation in Array

To represent binary tree structure in the array, consider each array index as a node, where these index of nodes for a parent, left the child and right child follow these expression. In Binary tree for zero-based array ,the root node is stored at index 0; if i is the index of the current node, then

• parent(i) = floor((i-1) / 2) , where floor map a real number to the smallest leading integer.
• LeftChild(i) = 2*i + 1
• RightChild(i) = 2*i + 2

Steps for Heap Sort

1. Call the heapify() function on the array to make as Max Heap Binary Tree array where Maximum item on the first position.
2. Swap the first item of the array with the final item. Consider the size of the array by decrease one. Call heapify() on the root of a binary tree.
3. Repeat the above steps until the size of the unsorted heap is 1.

Note: The heapify() operation is run once, and is O(n) in performance. The swapping() function is O(log n) and is called n times. Therefore, the total performance of this heap sort algorithm is O(n + n log n) = O(n log n).

<h2>Heapsort Java Program</h2>
public class HeapSort {

public static void main(String []args)
{
int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
System.out.println("Before Heap Sorting :");
printArray(items);

//Perform heap sort
heapsort(items);

System.out.println("After Heap Sorting :");
printArray(items);
}

public static void heapsort(int items[])
{
int itemCount = items.length;

// Build heap (rearrange array)
for (int i = itemCount / 2 - 1; i &gt;= 0; i--)
heapify(items, itemCount, i);

// One by one extract an element from heap
for (int i=itemCount-1; i&gt;=0; i--)
{
// Move max root item to end
int temp = items[0];
items[0] = items[i];
items[i] = temp;

// call max heapify on the reduced heap
heapify(items, i, 0);
}
}

/**
* Call the heapify() function on the array of decrease size to make as Max Heap Binary
* Tree array where Maximum item on first position or root.
*/
static void heapify(int items[], int itemCount, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (l  items[largest])
largest = l;

// If right child is larger than largest so far
if (r  items[largest])
largest = r;

// If largest is not root
if (largest != i)
{
int swap = items[i];
items[i] = items[largest];
items[largest] = swap;

// Recursively heapify the affected sub tree
heapify(items, itemCount, largest);
}
}

static void printArray(int items[])
{
for (int item:items)
{
System.out.print(item + " ");
}
System.out.println();
}
}

Output

Before Heap Sorting :
2 6 3 8 4 1 5 0 
After Heap Sorting :
0 1 2 3 4 5 6 8