## DEV Community is a community of 696,672 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Heap sort algorithm

Aya Bouchiha
Full stack web developer

Hi, today we'll discuss the Heapsort algorithm, for better understanding this algorithm, you need to be familiar with Heap data structure if you're not, check this the complete guide to heap data structure

## Definition of Heapsort

Heapsort: is one of the most efficient sorting algorithms which is based on heap data structure

## Space and Time complexity of Heapsort

The space complexity of the heap sort algorithm is O(1)

Best case Average case Worst case
O(n log n) O(n log n) O(n log n)

## Heap sort approach

1. Covert the giving array to a max-heap
2. While the size of the heap is greater than 1:
1. After converting it, The root is the maximum value of the max-heap.
2. Replace the root with the last item of the max-heap.
3. Decrease the size of the heap.
4. Bubble down (heapify) the root.

## Implementation of Heap sort algorithm in python

### heapify function

``````def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1    # left = 2*i + 1
r = 2 * i + 2    # right = 2*i + 2

# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l

# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r

# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap

# Heapify the root.
heapify(arr, n, largest)
``````

### Heap sort function

``````def heapSort(arr):
n = len(arr)

# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)

# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
``````