Heap Sort

#!/usr/bin/evn python

# Function to create subtree
def heapify(data, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
 
    # Compare left child and root
    if l < n and data[i] < data[l]:
        largest = l
 
    # Compare right child and root
    if r < n and data[largest] < data[r]:
        largest = r
 
    # Change root, if needed
    if largest != i:
        data[i],data[largest] = data[largest],data[i]
 
        # Heapify the root
        heapify(data, n, largest)
 
# The main function to sort an data array of given size
def heapSort(data):
    n = len(data)
 
    # Build a maxheap
    for i in range(n, -1, -1):
        heapify(data, n, i)
 
    # One by one extract elements
    for i in range(n-1, 0, -1):
        data[i], data[0] = data[0], data[i]
        heapify(data, i, 0)
  
  
numList = [5,8,1,6,3,7,2,4,9]
print('Before sort:')
print(numList)
# Calling 'heapSort' function by passing number data array
heapSort(numList)
print('After sort:')
print(numList)


# ***** Output *****
Before sort:
[5, 8, 1, 6, 3, 7, 2, 4, 9]
After sort:
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Comments (0)

  • To add your comment please or

We use cookies to improve your experience on our site and to show you personalised advertising. Please read our cookie policy and privacy policy.

Got It!