heapq: Heap Sort Algorithm

Heap queue data structure implements the priority queue. In python, the heap sort algorithm is used through the heapq module as min-heap. Whenever any element is popped or pushed the heap.sort( ) maintains the heap invariant.

• Step 1 — Construct a Binary Tree with a given list of Elements.
• Step 2 — Transform the Binary Tree into Min Heap.
• Step 3 — Delete the root element from Min Heap using Heapify method.
• Step 4 — Put the deleted element into the Sorted list.
• Step 5 — Replace the root element with the last left most element if not present then replace it with the rightmost last element.
• Step 6 — Repeat the same until Min Heap becomes empty.
• Step 7 — Display the sorted list.

Example:

Input data: 7, 12, 6, 4, 2
         7(0)
        /   \
     12(1)   6(2)
    /   \
 4(3)    2(4)

The numbers in bracket represent the indices in the array 
representation.

Applying heapify procedure to index 1:
         7(0)
        /   \
    12(1)    3(2)
    /   \
5(3)    1(4)

Applying heapify procedure to index 0:
        12(0)
        /  \
     7(1)  3(2)
    /   \
 4(3)    1(4)
Deleting the element and storing it 

Program to implement the above-mentioned heapsort example:

let’s create the main function for sorting an array

Operations on the heap :

Heapify(iterable): Convert iterable into a heap datastructure

heappush(heap, element): Insert element inside the heap and maintains the order of the heap.

heappop(heap): Removes and returns the smallest element from the heap and maintains the order of the heap.

For working on some interesting examples of sorting you can go through the video mentioned below: