Heap Sort Algorithms

Heap Sort Algorithms
Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It can be seen as
an optimization over selection sort where we first find the max (or min) element and swap it with the last (or
first). We repeat the same process for the remaining elements. In Heap Sort, we use Binary Heap so that we
can quickly find and move the max element (In O(Log n) instead of O(n)) and hence achieve the O(n Log n)
time complexity.
Detailed Working of Heap Sort

To understand heap sort more clearly, let’s take an unsorted array and try to sort it using heap sort.
Consider the array: arr[] = {4, 10, 3, 5, 1}.
Consider the given array as Complete Binary Tree (For every index i, the left child is at index 2*i + 1 and
right at 2*i + 2.
Transform the array into max heap:

 To transform a heap into a max-heap, the parent node should always be greater than or equal to the
child nodes
o Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap
them to build a max-heap.
 Now, 4 as a parent is smaller than the child 5 , thus swap both of these again and the resulted heap
and array should be like this:
Perform heap sort: Remove the maximum element in each step (i.e., move it to the end position and
remove that) and then consider the remaining elements and transform it into a max heap.
 Delete the root element (10) from the max heap. In order to delete this node, try to swap it with the last
node, i.e. (1). After removing the root element, again heapify it to convert it into max heap.
o Resulted heap and array should look like this:
1
 Repeat the above steps and it will look like the following:
 Now remove the root (i.e. 4) again and perform heapify.
 Now remove the root (i.e. 3) again and perform heapify.
 Now when the root is removed once again it is sorted. and the sorted array will be like arr[] = {1, 3, 4,
5, 10} .
2
Complexity Analysis of Heap Sort
Time Complexity: O(n log n)
Auxiliary Space: O(log n), due to the recursive call stack. However, auxiliary space can be O(1) for
iterative implementation.
Heap Sort Algorithm

First convert the array into a max heap using heapify, Then one by one delete the root node of the Max-
heap and replace it with the last node and heapify. Repeat this process while size of heap is greater than 1.
 Build a max heap from the given input array.
 Repeat the following steps until the heap contains only one element:
o Swap the root element of the heap (which is the largest element) with the last element of the
heap.
o Remove the last element of the heap (which is now in the correct position).
o Heapify the remaining elements of the heap.
 The sorted array is obtained by reversing the order of the elements in the input array.
Important points about Heap Sort

 Heap sort is an in-place algorithm.
 Its typical implementation is not stable but can be made stable (See this)
 Typically 2-3 times slower than well-implemented QuickSort. The reason for slowness is a lack of
locality of reference.
# Python program for implementation of heap Sort
# To heapify subtree rooted at index i.

# n is size of heap
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
3
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)
# The main function to sort an array of given size
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)
# Driver's code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
# Function call
heapSort(arr)
N = len(arr)
print("Sorted array is")

for i in range(N):
print("%d" % arr[i], end=" ")
Output
Sorted array is
5 6 7 11 12 13
Advantages of Heap Sort

 Efficient Time Complexity: Heap Sort has a time complexity of O(n log n) in all cases. This makes it
efficient for sorting large datasets. The log n factor comes from the height of the binary heap, and it
ensures that the algorithm maintains good performance even with a large number of elements.
 Memory Usage – Memory usage can be minimal (by writing an iterative heapify() instead of a
recursive one). So apart from what is necessary to hold the initial list of items to be sorted, it needs no
additional memory space to work
 Simplicity – It is simpler to understand than other equally efficient sorting algorithms because it does
not use advanced computer science concepts such as recursion.
4
Disadvantages of Heap Sort
 Costly : Heap sort is costly as the constants are higher compared to merge sort even if the time
complexity is O(n Log n) for both.
 Unstable : Heap sort is unstable. It might rearrange the relative order.
 Inefficient: Heap Sort is not very efficient because of the high constants in the time complexity.

Heap Sort Algorithms

Uploaded by

Copyright:

Available Formats

Heap Sort Algorithms

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Heap Sort Algorithms

Uploaded by

Copyright:

Available Formats

Heap Sort Algorithms

Detailed Working of Heap Sort

Transform the array into max heap:

 Now remove the root (i.e. 4) again and perform heapify.

 Now remove the root (i.e. 3) again and perform heapify.

Heap Sort Algorithm

Important points about Heap Sort

# Python program for implementation of heap Sort

# To heapify subtree rooted at index i.

def heapify(arr, N, i):

# See if left child of root exists and is

# See if right child of root exists and is

# Change root, if needed

# Heapify the root.

# The main function to sort an array of given size

# One by one extract elements

print("Sorted array is")

Advantages of Heap Sort

You might also like