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[0] = arr[0], 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[0]
        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[0]
            self.heap[0] = 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

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

people.sort(compare_people_by_age)