A Heap is a tree-based data structure that is commonly used to implement priority queues. There are two primary types of heaps: Min Heap and Max Heap.

In a Min Heap, the root node is the smallest element, and each parent node is smaller than or equal to its children. Conversely, in a Max Heap, the root node is the largest element, and each parent node is greater than or equal to its children.

Key Characteristics

• Completeness: All levels of the tree are fully populated except for possibly the last level, which is filled from left to right.
• Heap Order: Each parent node adheres to the heap property, meaning it is either smaller (Min Heap) or larger (Max Heap) than or equal to its children.

Visual Representation

Common Implementation: Binary Heap

The Binary Heap is a popular heap implementation that is essentially a complete binary tree. The tree can represent either a Min Heap or Max Heap, with sibling nodes not being ordered relative to each other.

Array Representation and Index Relationships

Binary heaps are usually implemented using an array, where:

• Root: heap[0]
• Left Child: heap[2 * i + 1]
• Right Child: heap[2 * i + 2]
• Parent: heap[(i - 1) // 2]

Core Operations

1. Insert: Adds an element while maintaining the heap order, generally using a “heapify-up” algorithm.
2. Delete-Min/Delete-Max: Removes the root and restructures the heap, typically using a “heapify-down” or “percolate-down” algorithm.
3. Peek: Fetches the root element without removing it.
4. Heapify: Builds a heap from an unordered collection.
5. Size: Returns the number of elements in the heap.

Performance Metrics

• Insert: $O(\log n)$
• Delete-Min/Delete-Max: $O(\log n)$
• Peek: $O(1)$
• Heapify: $O(n)$
• Size: $O(1)$

Code Example: Min Heap

Here is the Python code:

# Utility functions for heapify-up and heapify-down
def heapify_up(heap, idx):
    parent = (idx - 1) // 2
    if parent >= 0 and heap[parent] > heap[idx]:
        heap[parent], heap[idx] = heap[idx], heap[parent]
        heapify_up(heap, parent)

def heapify_down(heap, idx, heap_size):
    left = 2 * idx + 1
    right = 2 * idx + 2
    smallest = idx
    if left < heap_size and heap[left] < heap[smallest]:
        smallest = left
    if right < heap_size and heap[right] < heap[smallest]:
        smallest = right
    if smallest != idx:
        heap[idx], heap[smallest] = heap[smallest], heap[idx]
        heapify_down(heap, smallest, heap_size)

# Complete MinHeap class
class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        heapify_up(self.heap, len(self.heap) - 1)

    def delete_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        heapify_down(self.heap, 0, len(self.heap))
        return min_val

    def peek(self):
        return self.heap[0] if self.heap else None

    def size(self):
        return len(self.heap)