Open In App

Binary Heap in Python

Last Updated : 12 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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())

Output
Minimum element in the heap: 2
Deleted minimum element: 2
Minimum element in the heap after deletion: 3




Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads