# Heap Sort in Python

Sure! Here’s an implementation of Heap Sort in Python:

```def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[i] < arr[l]:
largest = l

if r < n and arr[largest] < arr[r]:
largest = r

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]  # swap

heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

# Build a maxheap.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

# Extract elements one by one.
for i in range(n - 1, 0, -1):
arr[i], arr = arr, arr[i]  # swap
heapify(arr, i, 0)

return arr
```

To use this implementation, simply call the `heap_sort()` function with an array as its argument. For example:

```arr = [5, 3, 8, 4, 2, 7, 1, 10]
sorted_arr = heap_sort(arr)
print(sorted_arr)  # Output: [1, 2, 3, 4, 5, 7, 8, 10]
```

The `heapify()` function is used to maintain the heap property of the array. It takes an array `arr`, its length `n`, and an index `i` as its arguments. The function compares the element at index `i` with its left child `l` and right child `r`, and swaps it with the larger child if necessary. The `heap_sort()` function first builds a maxheap out of the array, then repeatedly extracts the maximum element from the heap and puts it at the end of the array until the entire array is sorted in ascending order.

### What is Heap Sort?:

Heap Sort is a comparison-based sorting algorithm that works by turning the input array into a binary heap structure, where the largest element is at the root of the heap. It then repeatedly swaps the root element with the last element of the heap, reduces the size of the heap by one, and heapifies the resulting tree to maintain the heap property. This process is repeated until the entire array is sorted.

Heap Sort has a worst-case time complexity of O(n log n), making it an efficient algorithm for large datasets. However, it requires O(n) auxiliary space to create the heap structure, which can be a disadvantage for memory-constrained systems. Additionally, Heap Sort is not a stable sorting algorithm, meaning that the relative order of equal elements may not be preserved after sorting.

Despite these limitations, Heap Sort is a popular sorting algorithm due to its simplicity and efficiency. It is commonly used in embedded systems, where memory is limited and a simple implementation is required.

### Heap Data Structure:

Heap data structure is a specialized tree-based data structure that satisfies the heap property. In a heap, each parent node is larger or smaller (depending on the type of heap) than its child nodes.

There are two types of heaps:

1. Max Heap: In a max heap, the parent node is always larger than its child nodes. The root node of the heap is the largest element in the heap.
2. Min Heap: In a min heap, the parent node is always smaller than its child nodes. The root node of the heap is the smallest element in the heap.

A heap can be implemented as a binary tree or an array. In a binary tree implementation, each node has two child nodes. In an array implementation, the child nodes of a node at index i are located at 2i+1 and 2i+2.

Heaps are commonly used for implementing priority queues, where the element with the highest (or lowest) priority is always at the root of the heap. They are also used for heap sort, which is an efficient sorting algorithm that uses a max heap to sort an array in ascending order.

The operations that can be performed on a heap include heapify, which maintains the heap property after an element is added or removed, and insert and delete operations, which add or remove an element from the heap while maintaining the heap property.

### Implementation:

Here’s an example implementation of a binary max heap in Python using an array:

```class MaxHeap:
def __init__(self):
self.heap = []

def parent(self, i):
return (i - 1) // 2

def left_child(self, i):
return 2 * i + 1

def right_child(self, i):
return 2 * i + 2

def get_max(self):
if len(self.heap) > 0:
return self.heap
else:
return None

def insert(self, value):
self.heap.append(value)
current_index = len(self.heap) - 1
while current_index > 0 and self.heap[current_index] > self.heap[self.parent(current_index)]:
self.heap[current_index], self.heap[self.parent(current_index)] = self.heap[self.parent(current_index)], self.heap[current_index]
current_index = self.parent(current_index)

def extract_max(self):
if len(self.heap) == 0:
return None
elif len(self.heap) == 1:
return self.heap.pop()
else:
max_value = self.heap
self.heap = self.heap.pop()
self.max_heapify(0)
return max_value

def max_heapify(self, i):
left = self.left_child(i)
right = self.right_child(i)
largest = i
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self.max_heapify(largest)
```

This implementation includes methods for inserting a new element, extracting the maximum element, and getting the maximum element without removing it. The `max_heapify` method is used to maintain the max heap property after an element is removed. The time complexity for insertion and extraction is O(log n), while the time complexity for getting the maximum element is O(1).

To use this implementation, create a new instance of the `MaxHeap` class and call its methods as needed. For example:

```heap = MaxHeap()
heap.insert(5)
heap.insert(8)
heap.insert(3)
print(heap.get_max())  # Output: 8
print(heap.extract_max())  # Output: 8
print(heap.get_max())  # Output: 5
```

### Sorting Custom Objects:

To sort a list of custom objects, you can define a custom comparison function and pass it to the `sort()` method of the list. The comparison function should take two objects and return -1 if the first object should come before the second, 0 if they are equal, and 1 if the second object should come before the first.

For example, let’s say we have a list of `Person` objects, each with a `name` and an `age` attribute. We want to sort the list by age, with older people coming first in the list. We could define a comparison function like this:

```def compare_people_by_age(person1, person2):
if person1.age < person2.age:
return 1
elif person1.age == person2.age:
return 0
else:
return -1
```

Then we could sort the list of `Person` objects like this:

```people = [
Person('Alice', 25),
Person('Bob', 30),
Person('Charlie', 20)
]

people.sort(compare_people_by_age)
```

After the `sort()` call, the `people` list will be sorted by age, with `Bob` coming first, followed by `Alice`, and then `Charlie`.

Note that if you don’t specify a comparison function, the `sort()` method will try to compare the objects using the default comparison operator, which may not work for custom objects. In that case, you may get a `TypeError` saying that the objects are not comparable.

### Comparison between Heap sort and Other Algorithm:

Here’s a comparison between heap sort and a few other sorting algorithms in terms of time complexity, space complexity, and stability:

1. Heap Sort:
• Time Complexity: O(n log n)
• Space Complexity: O(1)
• Stability: Not stable
1. Merge Sort:
• Time Complexity: O(n log n)
• Space Complexity: O(n)
• Stability: Stable
1. Quick Sort:
• Time Complexity: O(n log n) average case, O(n^2) worst case
• Space Complexity: O(log n) average case, O(n) worst case
• Stability: Not stable
1. Insertion Sort:
• Time Complexity: O(n^2)
• Space Complexity: O(1)
• Stability: Stable
1. Selection Sort:
• Time Complexity: O(n^2)
• Space Complexity: O(1)
• Stability: Not stable

Heap sort has a time complexity of O(n log n), which is the same as merge sort, and better than selection sort and insertion sort. However, quick sort has an average-case time complexity of O(n log n), and can be faster than heap sort in some cases. The space complexity of heap sort is O(1), which is better than merge sort and quick sort. However, it’s worse than insertion sort and selection sort, which have a space complexity of O(1).

Heap sort is not a stable sorting algorithm, which means that it may change the relative order of equal elements in the input. This is in contrast to merge sort and insertion sort, which are stable sorting algorithms. Quick sort and selection sort are also not stable.

Overall, heap sort can be a good choice for sorting large arrays in place, where space is a concern. However, it may not be the best choice if stability is important or if the input is mostly sorted or nearly sorted, in which case insertion sort or quick sort might be faster.

### Conclusion:

In conclusion, heap sort is a comparison-based sorting algorithm that uses the heap data structure to sort elements in place. It has a time complexity of O(n log n) and a space complexity of O(1), making it a good choice for sorting large arrays in place where space is a concern. However, heap sort is not stable, and may change the relative order of equal elements in the input. If stability is important or the input is mostly sorted or nearly sorted, other sorting algorithms like merge sort or insertion sort might be a better choice. Additionally, quick sort can be faster than heap sort in some cases, especially when the input is random.