What is a Heap? #
 TreeBased Data Structure: A heap is essentially a specialized binary tree (nearly complete – all levels filled except maybe the last, with nodes filled left to right).
 Heap Property: A heap maintains a critical property:
 Max Heap: The key (or value) of each node is always greater than or equal to the keys of its children. The root node has the largest value.
 Min Heap: The key of each node is always less than or equal to the keys of its children. The root node has the smallest value.
Common Heap Operations #

Insert (push):
 Add the new element to the end of the heap (bottom of the tree).
 “Bubble up” (or heapify up): Compare the new element with its parent. If it violates the heap property, swap them. Continue swapping upwards until the property is restored.

Extract Max/Min (pop):
 The root node holds the maximum (maxheap) or minimum (minheap) value.
 Remove the root and replace it with the last element in the heap.
 “Bubble down” (or heapify down): Compare the new root with its children. If it violates the heap property, swap it with the larger (maxheap) or smaller (minheap) child. Continue swapping downwards until the property is restored.

Peek: Access the root element (maximum or minimum) without removing it.
Implementation #
Heaps are often implemented using arrays rather than explicit tree structures with pointers. This is due to the implicit structure of a complete binary tree:
 Elements can be placed into an array level by level.
 Parent and children indices can be calculated:
 For an element at index
i
: Parent:
(i  1) // 2
 Left Child:
2 * i + 1
 Right Child:
2 * i + 2
 Parent:
 For an element at index
Time Complexity (Big O Notation)
 Insert & Extract Max/Min: O(log n) due to the bubbling up/down operation (the height of a balanced tree is logarithmic).
 Peek: O(1) (constant time)
Space Complexity
 O(n)  where ’n’ is the number of elements in the heap.
Why Use Heaps? #
 Priority Queues: Heaps are the natural choice to implement priority queues. Get the highest/lowest priority element efficiently.
 Sorting: Used in the algorithm Heapsort.
 Graph Algorithms: Often found in algorithms like Dijkstra’s shortest path.