# Heap Sort in Data Structure

Heap Sort

A heap is a tree-based data structure that has specific properties.

• Heap is always a complete binary tree (CBT). That is, all the nodes of the tree are completely filled.
• If the value placed in each node is greater than or equal to its two children, then that heap is called max heap.
• If the value placed in each node is less than or equal to its two children, then that heap is called min-heap.
• If you want to sort the list in ascending order (increasing order), then you create the min-heap.
• If you want to sort the list in descending order (decreasing order), then you create the max heap.

### Selection sort algorithm

```Heapsort (A)
Build_Max_heap(A)
for i ? length[A] down to 2
do exchange A[i] ? A
heapsize(A) ? heapsize (A – 1)
Max_heapify (A, 1)  ```

This algorithm is for max heap sort.

Step 1: Create a new node.

Step 2: Assign a value to the node.

Step 3: Compare the value of the child node with the value of the parent node.

Step 4: If the child node value is greater than the parent node value, then interchange them.

Step 5: Repeat steps 3 and 4 until the heap is sorted correctly.

```Build_Max_heap(A)
heapsize(A) ? length[A]
for i ? length[A / 2] down to 1
Max_heapify (A, i)  ```
```Max_heapify (A, i)
l ? left[i]
r ? right[i]if l <= heapsize(A) and A[l] > A[i]
then largest ? l
also, largest ? iif r <= heapsize(A) and A[r] > A[largest]then largest ? rdo if i ? largestexchange A[i]  ? A[largest]Max_heapify (A, largest)  ```

### Heap sort program in C language

```#include<stdio.h>
int val;
void heapify(int arr[], int size, int i)
{
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < size && arr[left] >arr[largest])         largest = left;      if (right < size && arr[right] > arr[largest])         largest = right;      if (largest != i)
{
val = arr[i];
arr[i]= arr[largest];
arr[largest] = val;
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size)
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
for (i=size-1; i>=0; i--)
{
val = arr;
arr= arr[i];
arr[i] = val;
heapify(arr, i, 0);
}
}
void main()
{
int arr[] = {20, 50, 40, 10, 90, 80, 60, 70, 30, 100};
int i;
int size = sizeof(arr)/sizeof(arr);
heapSort(arr, size);
printf("heap sorted elements\n");
for (i=0; i<size; ++i)
printf("%d\n",arr[i]);   }    ```

Output

```heap sorted elements
10
20
30
40
50
60
70
80
90
100  ```

### Heap sort program in java language

```public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;        // Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr, n, i);
}                // Heap sort
for (int i = n - 1; i >= 0; i--)
{
int temp = arr;
arr = arr[i];
arr[i] = temp;             // Heapify root element
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{       // Find largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])    largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;            // Swap and continue heapifying if root is not largest
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}              // Function to print an array
static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}            // Driver code   public static void main(String args[])
{
int arr[] = { 20, 50, 40, 10, 90, 80, 60, 70, 30, 100 };
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("heap sorted elements");
printArray(arr);
}
}```

Output

```heap sorted elements
10
20
30
40
50
60
70
80
90
100  ```