Binary Heap in Python
Last Updated :
12 Apr, 2024
A Binary Heap is a complete Binary Tree that is used to store data efficiently to get the max or min element based on its structure.
A Binary Heap is either a Min Heap or a Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in a Binary Heap. The same property must be recursively true for all nodes in the Binary Tree. Max Binary Heap is similar to MinHeap.
Examples of Min Heap:
10 10
/ \ / \
20 100 15 30
/ / \ / \
30 40 50 100 40
Binary Heap in Python
Implement a binary heap data structure in Python, which supports the following operations:
insert(key): Insert a new element into the heap.delete_min(): Delete the minimum element from the heap.get_min(): Get the minimum element from the heap without deleting it.is_empty(): Check if the heap is empty.
Approach:
A binary heap is a complete binary tree where the value of each parent node is less than or equal to the values of its children. The minimum element is at the root. The main operations are insert and delete_min.
1. Insert Operation:
- Add the new element at the end of the heap.
- Restore the heap property by repeatedly swapping the new element with its parent until the heap property is restored.
2. Delete Minimum Operation:
- Replace the root of the heap with the last element.
- Restore the heap property by repeatedly swapping the new root with its smallest child until the heap property is restored.
3. Get Minimum Operation:
- Return the root of the heap.
4. Check if the Heap is Empty:
- Check if the length of the heap is 0.
Code
Python3
class BinaryHeap:
def __init__(self):
self.heap = []
def is_empty(self):
return len(self.heap) == 0
def insert(self, key):
self.heap.append(key)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, index):
parent_index = (index - 1) // 2
while parent_index >= 0 and self.heap[parent_index] > self.heap[index]:
self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
index = parent_index
parent_index = (index - 1) // 2
def get_min(self):
if self.is_empty():
return None
return self.heap[0]
def delete_min(self):
if self.is_empty():
return None
min_value = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self._heapify_down(0)
return min_value
def _heapify_down(self, index):
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
smallest = index
if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
smallest = left_child_index
if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
smallest = right_child_index
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._heapify_down(smallest)
# Example Usage
heap = BinaryHeap()
# Insert elements
heap.insert(3)
heap.insert(2)
heap.insert(15)
heap.insert(5)
heap.insert(4)
heap.insert(45)
print("Minimum element in the heap:", heap.get_min())
# Delete minimum element
print("Deleted minimum element:", heap.delete_min())
print("Minimum element in the heap after deletion:", heap.get_min())
OutputMinimum element in the heap: 2
Deleted minimum element: 2
Minimum element in the heap after deletion: 3
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...