Write python code for heap sort.

 Heap Sort:

Here's an implementation of Heap Sort algorithm in Python:

def heap_sort(arr): # Build max heap n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from heap one by one for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # swap heapify(arr, i, 0) def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap heapify(arr, n, largest)

The above code defines two functions: heap_sort() and heapify(). The heap_sort() function takes an array as input and sorts it using the Heap Sort algorithm. The heapify() function is a helper function that is used to maintain the heap property of the array.

The heap_sort() function first builds a max heap from the array using the heapify() function. It starts by iterating from the middle of the array to the first element, and calls heapify() on each index to ensure that the subtree rooted at that index is a max heap.

Once the max heap is built, the function iterates through the array from the last element to the second element. It swaps the first element of the array (which is the largest element) with the current element being considered, and then calls heapify() on the first element to restore the heap property.

The heapify() function takes three arguments: the array arr, the size of the heap n, and the index i of the element to be checked. It first sets the index of the largest element to i. It then checks if the left child of i (at index 2*i+1) is greater than i. If it is, it sets the index of the largest element to the index of the left child. It does the same check for the right child of i (at index 2*i+2). If the index of the largest element is not equal to i, it swaps the elements at i and the index of the largest element, and then calls itself recursively on the index of the largest element to ensure that the subtree rooted at that index is a max heap.

To test the heap_sort() function, you can call it with an array as an argument:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] heap_sort(arr) print(arr)

The output of this code will be the sorted array [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9].