The heap data structure is a complete binary tree that satisfies the heap property. It is a specialized tree-based data structure that allows efficient access to the maximum (or minimum) element in a collection.

What is a Heap?

A heap is a complete binary tree where each node satisfies the heap property. The heap property differs based on whether it is a max heap or a min heap. In a max heap, for every node, the value of the parent node is greater than or equal to the value of its children nodes. Conversely, in a min heap, the value of the parent node is smaller than or equal to the value of its children nodes.

Implementation of a Heap

Heaps can be implemented using arrays or linked lists. The array-based implementation is more popular due to its space efficiency and faster random access. In this example, we will focus on the array-based implementation.

Array Representation

To store a heap in an array, we use the following formulas:

• The root element is stored at index 0.
• For any node at index i, its left child is stored at index 2*i + 1.
• For any node at index i, its right child is stored at index 2*i + 2.
• The parent of any node at index i is stored at index (i-1)/2.

Operations on a Heap

The basic operations supported by a heap are:

1. Insertion: Adding an element to the heap.
2. Deletion: Removing the maximum (or minimum) element from the heap.
3. Peek: Retrieving the maximum (or minimum) element without removing it.
4. Heapify: Rearranges the elements in the heap to maintain the heap property.

Python Implementation

class Heap:
    def __init__(self):
        self.heap = []
        
    def insert(self, value):
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)
        
    def delete(self):
        if not self.is_empty():
            self.heap[0] = self.heap[-1]
            self.heap.pop()
            self._sift_down(0)
        
    def peek(self):
        if not self.is_empty():
            return self.heap[0]
        
    def is_empty(self):
        return len(self.heap) == 0
    
    def _sift_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[parent_index] < self.heap[index]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            self._sift_up(parent_index)
        
    def _sift_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        largest = index
        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
            largest = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
            largest = right_child_index
        if largest != index:
            self.heap[largest], self.heap[index] = self.heap[index], self.heap[largest]
            self._sift_down(largest)

Conclusion

The heap data structure is a powerful tool for managing data in an organized and efficient manner. Whether it’s finding the maximum element or sorting a collection, heaps can provide fast and reliable solutions. Understanding how heaps work and implementing them in your code can greatly enhance your ability to solve a wide range of problems efficiently.

#datastructure #heap