1.

Definition of Heap
A Heap is a complete binary tree (all levels completely filled except possibly the last, and the
last level has all keys as left as possible) which satisfies the heap property.

There are two main types of heaps:

● Min Heap: The parent is less than or equal to its children → the smallest element is at the
root.
● Max Heap: The parent is greater than or equal to its children → the largest element is at
the root.

Heap is typically implemented using an array.

2. Properties of Heap

Property Description
Shape Complete binary tree
Heap Order Parent node is smaller (min heap)
or larger (max heap) than children
Time for Insertion/Deletion O(log n)
Time for Accessing Min/Max O(1) (since it's the root)

3. Use Cases / Where Heaps Are Applied

Application Explanation
Priority Queue Heap is used to implement priority
queues efficiently
Top K Elements For finding top or smallest K
elements in O(n log k)
Heap Sort In-place sorting using heap (max
heap)
Median of Stream Min heap + max heap combo to
maintain running median
Dijkstra’s Algorithm For efficiently getting the smallest
distance vertex
Merge K Sorted Lists / Arrays Min-heap helps merge k lists in
 O(N log k)

4. How to Apply Heaps in Problems

You apply heap when:
● You need frequent access to the min or max value.
● You need to maintain a dynamic set of elements where you perform insertions +
deletions.
● You need to solve top K / smallest K / largest K problems.
● You're merging multiple sorted inputs efficiently.
● You want to simulate priority-based processing.

5. Java Implementation Tip

Java offers:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

7. Benefits of Using Heap

Benefit Explanation
Fast Access O(1) access to min/max
Efficient Updates O(log n) insert/delete
Dynamic Adapts to changes in the dataset
Memory Efficient In-place heap sort possible
Versatile Works for sorting, streaming,
scheduling, and more

8. Example Problems

Problem Heap Used Why

Find K Largest Min Heap of size K Maintain top K
Elements efficiently
Merge K Sorted Lists Min Heap Get smallest head
each time
 Running Median Two Heaps (Min + Balance left/right
Max) halves
Task Scheduler Max Heap Pick most frequent
task first
Top K Frequent Min Heap or Bucket Frequency
Elements Sort prioritization
Dijkstra’s Algorithm Min Heap Pick shortest path
node quickly

Definition: What is K-Way Merge?

K-Way Merge is a pattern used to merge K sorted lists/arrays into a single fully sorted list. It
extends the idea of merging two sorted arrays (like in Merge Sort) to K arrays using a min-heap
(or priority queue).

Core Idea (Intuition)

Instead of comparing all elements in all arrays, we maintain a min-heap of the current smallest
element from each list.
● Always extract the minimum element from the heap.
● Push the next element from the same list (from where the min came) into the heap.
● Repeat until all elements are merged.

Example Problem:
"Merge K sorted arrays into one sorted array"

Step-by-step:
. Initialize min-heap of size K
Each heap entry stores: (value, arrayIndex, elementIndex)
. Push first element from each of the K arrays into the heap
. While heap is not empty:
○ Pop the smallest element
○ Add it to result array
○ Push the next element from that array into the heap (if exists)
. Continue until all arrays are exhausted.
# Problem Title Type Description
1 Kth Largest Max Heap Find the Kth
Element in an largest using a
Array max/min heap
2 Top K Frequent Min Heap Use hashmap +
Elements heap to track
frequency
3 Merge K Sorted Min Heap Merge using
Lists priority queue of
list nodes
4 Find Median Min/Max Heap Use two heaps
from Data to maintain
Stream median
5 K Closest Max Heap Use heap to
Points to Origin keep top K
closest points
6 Task Scheduler Max Heap Greedy + max
heap of task
frequencies
7 Reorganize Max Heap Heap to always
String pick the most
frequent char
8 Kth Smallest Min Heap Matrix traversal
Element in a using heap
Sorted Matrix
9 Minimum Cost Min Heap Greedy strategy
to Connect using priority
Ropes queue
10 Last Stone Max Heap Smash top 2
Weight stones
 repeatedly
11 Sliding Window Min + Max Heap Track medians
Median as window
moves
12 Sort Characters Max Heap Sort based on
by Frequency frequency using
heap
13 Kth Largest Min Heap Maintain k-sized
Element in a heap in stream
Stream
14 Trapping Rain Min Heap Dijkstra-like BFS
Water II using heap
15 Smallest Range Min Heap Use heap to
Covering track smallest
Elements from range
K Lists