Heap Data Structure

The heap data structure is a binary tree-based data structure that satisfies the heap property. It is commonly implemented as an array, where the parent-child relationships are determined by the indices of the array elements. There are two main types of heaps: max heaps and min heaps.

Max Heap: In a max heap, every parent node has a value greater than or equal to the values of its children. The maximum value is stored at the root of the heap.

Min Heap: In a min heap, every parent node has a value less than or equal to the values of its children. The minimum value is stored at the root of the heap.

Here are some key operations supported by a heap:

Insertion: Adding a new element to the heap while maintaining the heap property.
Deletion: Removing an element (usually the root) from the heap while maintaining the heap property.
Peek: Viewing the element at the root of the heap without removing it.
Heapify: Converting an array into a heap by rearranging its elements to satisfy the heap property.

Here’s an example of a max heap implemented using the heapq module in Python:

import heapq

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

    def insert(self, value):
        heapq.heappush(self.heap, -value)  # Use negative values for max heap

    def delete_max(self):
        if self.is_empty():
            return None
        return -heapq.heappop(self.heap)  # Use negative values for max heap

    def peek_max(self):
        if self.is_empty():
            return None
        return -self.heap[0]  # Use negative values for max heap

    def is_empty(self):
        return len(self.heap) == 0

# Example usage:
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(5)
max_heap.insert(20)

print("Max element:", max_heap.peek_max())  # Output: 20
print("Deleted max element:", max_heap.delete_max())  # Output: 20
print("Max element after deletion:", max_heap.peek_max())  # Output: 10

In this example:

The MaxHeap class represents a max heap.
The insert() method inserts a new element into the heap while maintaining the heap property.
The delete_max() method removes and returns the maximum element from the heap.
The peek_max() method returns the maximum element from the heap without removing it.
The is_empty() method checks if the heap is empty.

The heapq module in Python provides efficient heap operations, and by using negative values, we can easily implement a max heap while still leveraging the module’s functionality.

Time Complexity

Operation	Best Case	Average Case	Worst Case	Space Complexity
Insertion	(O(\log n))	(O(\log n))	(O(\log n))	(O(1))
Deletion	(O(\log n))	(O(\log n))	(O(\log n))	(O(1))
Peek	(O(1))	(O(1))	(O(1))	(O(1))
Heapify	(O(n))	(O(n))	(O(n))	(O(1))

Explanation:

Insertion: Adding a new element to a heap involves inserting it at the end of the heap array and then restoring the heap property by performing a logarithmic number of “swaps” (upward movement) to maintain the heap property. The worst-case time complexity for insertion is (O(\log n)), where (n) is the number of elements in the heap. Since insertion only involves modifying the heap in-place, the space complexity is (O(1)).
Deletion: Removing the root element (usually the maximum or minimum value) from a heap requires replacing it with the last element in the array and then restoring the heap property by performing a logarithmic number of “swaps” (downward movement) to maintain the heap property. The worst-case time complexity for deletion is (O(\log n)), where (n) is the number of elements in the heap. Since deletion only involves modifying the heap in-place, the space complexity is (O(1)).
Peek: Retrieving the root element (maximum or minimum value) of a heap without removing it has a constant time complexity of (O(1)) in all cases. This operation simply involves accessing the first element of the heap array. Since no additional memory is used, the space complexity is also (O(1)).
Heapify: Building a heap from an unsorted array (heapify operation) involves rearranging the elements of the array to satisfy the heap property. The worst-case time complexity for heapify is (O(n)), where (n) is the number of elements in the array. This is because the heapify process involves “bubbling down” each non-leaf node to its correct position, starting from the last non-leaf node and moving upwards. The space complexity is (O(1)) because the heapify operation is performed in-place, modifying the existing array.