The heapsort test algorithm for python def heapify(arr, n, i): largest = i # Initialize largest
Fantastic news! We've Found the answer you've been seeking!
Question:
The heapsort test algorithm for python
- 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[i] < 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)
- def heapSort(arr):
- n = len(arr)
- # Build a max heap.
- 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[i], arr[0] = arr[0], arr[i] # swap
- heapify(arr, i, 0)
- # Testing the heap sort algorithm
- arr = [12, 11, 13, 5, 6, 7]
- heapSort(arr)
- print("Sorted array is:", arr)
Please answer:
- Find the best case, worst case, and average case in time and space complexity. Explain.
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date: