Heaps

A Heap is a specialized binary tree-based data structure that satisfies the heap property:

Max-Heap: Every parent node is a greater than or equal to its children. The largest element is always at the root.
Min-Heap: Evert parent node is less than or equal to its children. The smallest element is always at the root.

A heap is typically implemented as an array because the tree structure can be efficiently mapped to indices:

Parent of i: Math.floor( (i-1) / 2 )
Left child of i: 2 * i + 1
Right child of i: 2 * i + 2

Properties of a Heap:

A heap is a specialized tree-based data structure that satisfies two main properties:

Complete Binary Tree Property:

Every level of the tree is completely filled except possibly the last level.

The last level is filled from left to right without any gaps.

Heap Order Property:

- Max Heap Order Property:

For every node N, the value of N greater than or equal to the children of N.

The maximum element is at the root.

- Min Heap Order Property:

For every node N, the value of N is lesser than or equal to the children of N

The minimum element is at the root.

Implement Min-Heap

1. Design an algorithm that implement a Min-Heap data structure.

A min heap is a complete binary tree where the value of each node is less than or equal to its children.

The heap should support the following operations:

push(x): Insert an element x into the heap.
pop(): Remove and return the smallest element (root).
peek(): Return the smallest element without removing it.
delete(index): Remove the element at a specific index.
heapify(): Reorganize to satisfy the heap property.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input	push(1), pop()	push many elements, then multiple pop/delete calls	pop/peek/delete on empty heap, delete invalid index
Output	1	Maintains heap invariant across all operations	Throws error, returns null/undefined appropriately
Explanation	Heap remains valid with minimum reordering	Tests bubble-up and heapify-down operations under stress	Verifies stability, boundary handling, exception safety

Implement Max-Heap

2. Design an algorithm that implement a Max-Heap data structure.

A max heap is a complete binary tree where the value of each node is greater than or equal to its children.

The heap should support the following operations:

push(x): Insert an element x into the heap.
pop(): Remove and return the smallest element (root).
peek(): Return the largest element without removing it.
delete(index): Remove the element at a specific index.
heapify(): Reorganize to satisfy the heap property.

Parameter \ Case	Best Case	Worst Case	Edge Case
Input	push(10), pop(), peek() on 1-element heap	Multiple push() and pop() on a large heap	Empty heap pop(), peek() or delete(index) out of bounds
Output	Returns expected max element quickly	Correctly maintains max-heap on every insert/delete	Gracefully returns null, throws error, or returns default (e.g., undefined)
Explanation	Heap is already valid or needs minimal reordering	Requires bubbling down/up through entire tree height	Tests boundary conditions and robustness of implementation

Kth Largest Element

3. Given an unsorted array of integers nums and an integer k. Design an algorithm that return the kth largest element in the array.

Parameter \ Case	Best case	Worst case	Edge case
input	nums = [9, 1, 2, 3], k = 1	nums = [1, 2, ..., 10⁵], k = 1	[[0]], [[1]], [[2]]
Output	9	10⁵	3
Explanation	The max element is first — fast result	Needs to iterate all 10⁵ elements and track top	Only one number in the array — it's the answe

Merge K Sorted Array

4. Given k sorted integer arrays of various lengths. Design an algorithm that merges all of them into a single sorted array.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	Arrays with all elements the same: [[1], [1], [1]]	Arrays of maximum size with no overlapping values	Some arrays empty: [[], [3], [], [1, 2]]
Output	[1, 1, 1]	Fully merged sorted array of size 10⁶	[1, 2, 3]
Explanation	All values identical → minimal movement in heap	Max values and full traversal of heap (heap grows to k)	Must handle and skip empty arrays correctly

Is this a Heap?

5. You are given the root node of a binary tree. Design an algorithm to check whether the tree represents a valid binary heap.

A binary heap must satisfy two properties:

Complete Binary Tree: All levels must be fully filled except possibly the last, and the last level's nodes must appear as far left as possible.
Heap Order Property: For a Max-Heap, every parent node must be greater than or equal to its children. For a Min-Heap, every parent node must be less than or equal to its children.

The algorithm should return true if the tree satisfies both conditions, otherwise return false.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	A perfect Max-Heap (e.g. complete, ordered)	Almost complete with violation at bottom or middle level	A tree with only 1 node or null
Output	true	false	true or false depending on heap rule
Explanation	All nodes follow both rules	Either order or completeness is violated (e.g., right child exists without left)	Single node satisfies both rules, or null is valid

Heapify and Sort

6. Given an unsorted array of integers. Design an algorithm that implement the Heap Sort algorithm using a Max-Heap to sort the array in ascending order. The algorithm should return the sorted array.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	[1, 2, 3, 4, 5] (already sorted)	[5, 4, 3, 2, 1] (descending order)	[], [7], [5, 5, 5, 5]
Output	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	[], [7], [5, 5, 5, 5]
Explanation	Minimal swaps needed	Every node must be heapified + swapped	Edge cases test stability and constraints

Merge K Sorted Linked Lists

1. Given k singly linked lists,where each linked list is sorted in ascending order.

Design an algorithm that will merge all the linked lists into one sorted linked list and return its head.

Linked List Node:


   class ListNode{
    constructor(value){
        this.value = value;
        this.next = null;
    }
   }

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	k = 3, each list has 1 element → [[1], [2], [3]]	k = 3, lists of equal large size → [[1,4,7], [2,5,8], [3,6,9]]	k = 0 or k > 0 with some/all lists empty → [], [[], [], []]
Output	[1, 2, 3]	[1, 2, 3, 4, 5, 6, 7, 8, 9]	[] if no lists; non-empty result if some lists have nodes
Explanation	Simple linear merge from three 1-element lists, heap operations minimal	All values interleave; each push/pop involves log(k) operations in heap	Must handle zero lists or some/all being empty without crashing or errors

Top K Frequent Elements

2. Given an integer array nums and an integer k. Design an algorithm that return the k most frequent elements in nums.

The frequency of an element is the number of times it appears in nums.
If multiple elements have the same frequency and complete for the last position(s) in the top k, any of those elements can be included.
The returned array must contain exactly k elements.

The output array can be in any order.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	nums = [1,1,1,2,2,3], k = 1	nums = [1,2,3,4,5,...,100000], k = 50000	nums = [], k = 0
Output	[1]	Any 50000 most frequent (all have freq 1)	[]
Explanation	One number dominates frequency count	All elements have same frequency, so any k	Empty input or asking for 0 most frequent → []

Median Tracker

3. Design a data structure that continuously accepts integers from a data stream and efficiently returns the median of all received numbers at any point in time.

Median Definition:

If the total count is odd, the median is the middle element.
if even, the median is the average of the two middle elements.

You must implement this using two heaps:

A Max-Heap to store the lower half of the numbers.
A Min-Heap to store the upper half of the numbers.

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	1 → 2 → 3	1000 elements in reverse sorted order	No elements or all identical (e.g., [5,5])
Output	2	Median calculated after many insertions	null or predefined behavior for empty
Explanation	Small input, heaps are balanced easily.	Requires frequent heap rebalancing.	Needs logic to handle 0 or same input values

Kth Smallest Element

4. Given an n * n matrix where each row and column is sorted in ascending order. Design an algorithm to find the kth smallest element in the matrix.

The matrix contains no duplicates.
The kth smallest means there are exactly k-1 elements in the matrix that are smaller than the result.
The algorithm should return the element itself (not the index).

Parameter\ Case	Best Case	Worst Case	Edge Case
Parameters	matrix = [[1]], k = 1	matrix = large 300x300 matrix, k = 90000	k = 1 or k = n*n
Output	1	Depends on last element, e.g., 10⁹ in a large matrix	matrix[0][0] for k = 1, matrix[n-1][n-1] for k = n*n
Explanation	Only one element to consider	All elements must be pushed or checked using a heap or binary search	Tests the lower and upper boundary of valid k values

- Fundamentals -