**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

- Call the heapify() function on the array to make as
**Max Heap Binary Tre**e array where Maximum item on the first position. - 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.
- 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 >= 0; i--) heapify(items, itemCount, i); // One by one extract an element from heap for (int i=itemCount-1; i>=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
```

## One thought on “[Sorting] Heapsort Program and Complexity (Big-O)”