18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N)

45 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N)

> DSA Blind 75 Notes by Rishabh - Topic 18

---

### 1. Heap Kya Hai? (Complete Binary Tree in a Flat Array 🏔️)

Heap ek Complete Binary Tree hoti hai jo flat array me bina kisi pointer ke represent hoti hai:

```
Array Index Rules (0-Indexed):
  Parent(i)      = (i - 1) // 2
  Left Child(i)  = 2 * i + 1
  Right Child(i) = 2 * i + 2
```

*   **Min-Heap:** Har parent apne children se chhota hota hai (`Root = Minimum Element`).
*   **Max-Heap:** Har parent apne children se bada hota hai (`Root = Maximum Element`).

---

### 2. Python `heapq` Module (Min-Heap by Default)

```python
import heapq

nums = [5, 7, 1, 3, 9]

# 1. In-place Heapify in O(N) Time:
heapq.heapify(nums) # nums becomes: [1, 3, 5, 7, 9]

# 2. Push & Pop in O(log N):
heapq.heappush(nums, 2)
min_val = heapq.heappop(nums) # 1

# 3. Max-Heap Trick in Python (Negate values!):
max_heap = [-x for x in [5, 7, 1, 3, 9]]
heapq.heapify(max_heap)
max_val = -heapq.heappop(max_heap) # 9
```

---

### 3. Why `heapify` is $O(N)$ and NOT $O(N \log N)$ 🔬

Bottom-up Sift-Down approach me leaf nodes (jo total $\frac{N}{2}$ hoti hain) 0 swaps karti hain, uske upar wali 1 swap, aur sirf root $\log N$ swaps karta hai.  
$$\sum_{h=0}^{\log N} \frac{N}{2^{h+1}} \cdot O(h) = O(N) \text{ (Mathematical Taylor Series Convergence!)}$$

---

### 4. Master Comparison Matrix

| Operation | Array / List | Balanced BST | Binary Heap |
| :--- | :--- | :--- | :--- |
| **Find Min/Max** | $O(N)$ (Unsorted) | $O(\log N)$ | ⚡ **$O(1)$ (Direct Root Index 0)** |
| **Insert** | $O(1)$ amortized | $O(\log N)$ | ⚡ **$O(\log N)$** |
| **Delete Min/Max** | $O(N)$ | $O(\log N)$ | ⚡ **$O(\log N)$** |
| **Build from $N$ items**| $O(N)$ | $O(N \log N)$ | ⚡ **$O(N)$ (`heapify`)** |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **Heap me random element delete ya search karna kitna time leta hai?** -> Search $O(N)$ leta hai kyunki Heap me BST jaisa horizontal sorted order nahi hota (sirf parent-child vertical order hota hai).
2. **Priority Queue aur Normal Queue me kya difference hai?** -> Normal queue FIFO order follow karti hai; Priority Queue hamesha highest priority (min ya max) element pehle pop karti hai.
3. **Heap Sort algorithm ki time aur space complexity kya hoti hai?** -> Time: $O(N \log N)$, Space: $O(1)$ in-place.

---
**Next Topic:** 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                