Min Heap Implementation in Python

A min-heap is a data structure that satisfies the heap property, which states that the value of each node is less than or equal to its children. It means that the minimum value of the heap is always stored at the root.

Here is the algorithm for building a min heap:

1. Create an empty list to represent the heap.
2. For each element in the input list, insert it into the heap using the insert function (described below).
3. Return the heap.

The insert function takes a heap and a value and adds the value to the heap while maintaining the heap property.

The algorithm for the insert function:

1. Add the new value to the end of the heap.
2. While the value is not at the root of the heap and its parent is greater than the value:
3. Swap the value with its parent.
4. Update the index of the value and its parent.
5. Return the updated heap.

Example:

Python program to implement this algorithm:

Output:

[1, 3, 5, 4, 8, 7]

The build_heap method starts by copying the input list into the heap array, and then calls the min_heapify method on each non-leaf node in the heap, starting from the bottom and working up. It ensures that the resulting heap satisfies the min-heap property.

• __init__: This method simply initializes an empty list to store the heap. Its time complexity is O(1) and its space complexity is O(1).
• parent, left_child, and right_child: These methods simply compute the indices of the parent and children of a given node. Their time complexity is O(1) and their space complexity is O(1).
• insert: This method inserts a value into the heap and restores the min heap property by swapping the new value with its parent as necessary. In the worst case, the new value may need to be swapped all the way up to the root of the tree, which takes O(log n) Therefore, the time complexity of insert is O(log n) and its space complexity is O(1).
• get_min: This method returns the minimum value in the heap, which is always the root of the tree. Its time complexity is O(1) and its space complexity is O(1).
• extract_min: This method removes the minimum value from the heap and restores the min-heap property by swapping the last element in the heap with the root and then swapping the root with its smaller child as necessary. In the worst case, the new root may need to be swapped all the way down to the leaves of the tree, which takes O(log n) Therefore, the time complexity of extract_min is O(log n) and its space complexity is O(1).
• build_heap: This method builds a min heap from an input list by calling min_heapify on each non-leaf node in the heap. Each call to min_heapify takes O(log n) time, and there are O(n) non-leaf nodes in the heap, so the total time complexity of build_heap is O(n log n). Its space complexity is O(n), since it needs to copy the input list into the heap array.
• min_heapify: This method restores the min heap property for a node and its children by swapping the node with its smallest child as necessary. In the worst case, the node may need to be swapped all the way down to the leaves of the tree, which takes O(log n) Therefore, the time complexity of min_heapify is O(log n) and its space complexity is O(1).
• __len__: This method returns the number of elements in the heap, which is simply the length of the heap list. Its time complexity is O(1) and its space complexity is O(1).

Overall, the MinHeap class has a worst-case time complexity of O(n log n) for building the heap, and O(log n) for insertions, extractions, and min heapify operations. Its worst-case space complexity is O(n), due to the need to copy the input list into the heap array when building the heap.

One alternative approach is to use a binary heap represented as a binary tree, where each node has at most two children. In this representation, the heap is stored in a list where the parent of a node at index i is at index (i-1)//2, and the left and right children of a node at index i are at indices 2*i+1 and 2*i+2, respectively.

Example:

Output:

[1, 3, 5, 4, 8, 7]

Explanation:

In this implementation, the __init__ method takes an optional lst argument that is used to build the heap if it is provided. The build_heap method takes a list as input and modifies the heap in-place to ensure that it satisfies the min-heap property.

The two approaches are essentially the same. In both cases, we have implemented a binary min-heap using an array to store the heap, and we have used the min_heapify method to ensure that the min-heap property is satisfied after each insertion or deletion operation.

The only difference between the two implementations is that in the first approach, the build_heap method takes a list as input and creates a new heap from scratch, whereas in the second approach, the build_heap method modifies an existing heap that is represented as an array.