The Heap is a specialized tree-based data structure that satisfies the heap property:
- Max-Heap: The key of the parent node is always greater than or equal to the keys of its children.
- Min-Heap: The key of the parent node is always less than or equal to the keys of its children.
Heaps are primarily used in scenarios requiring priority queues, sorting algorithms (e.g., heap sort), and efficient retrieval of minimum or maximum elements. Due to their structure, heaps are highly efficient for operations like inserting, deleting, or finding elements in ( O(\log n) ) time.
This repository includes a variety of problems that involve:
- Heap basics and STL implementations.
- Common heap operations (e.g., finding kth largest/smallest elements).
- Advanced applications of heaps in algorithms like merging sorted arrays, finding medians in a stream, and range problems in multiple lists.
Each problem folder includes:
- Problem statement and description.
- Solutions with optimized approaches (when applicable).
- Links to the problem on LeetCode or GeeksforGeeks, along with relevant explanations.
Explore the Heap Problems section to gain insights into solving real-world challenges using heaps efficiently!
No | Problem Name | Description | LeetCode | GFG |
---|---|---|---|---|
01 | Example | Basic heap operations. | Non | Non |
02 | Example - STL | Demonstration of heap operations using STL. | Non | Non |
03 | Kth Smallest | Find the kth smallest element in an array. | Non | Link |
04 | Check Completeness of a Binary Tree | Verify if a binary tree is complete. | Link | Non |
05 | Is Binary Tree Heap | Determine if a binary tree satisfies heap property. | Non | Link |
06 | Merge Two Binary Max Heaps | Merge two max heaps into one. | Non | Link |
07 | Minimum Cost of Ropes | Find the minimum cost of connecting ropes. | Non | Link |
08 | Convert BST to Min Heap | Convert a binary search tree to a min-heap. | Non | Link |
09 | Convert BST to Max Heap | Convert a binary search tree to a max-heap. | Non | Link |
10 | BST to Max Heap | Another approach to convert BST to max-heap. | Non | Link |
11 | Kth Largest Sum Contiguous Subarray | Find the kth largest sum in contiguous subarrays. | Non | Link |
12 | Merge K Sorted Arrays | Merge k sorted arrays into a single sorted array. | Non | Link |
13 | Merge K Sorted Lists | Merge k sorted linked lists into a single sorted list. | Link | Non |
14 | Smallest Range in K Lists | Find the smallest range that includes elements from k lists. | Non | Link |
15 | Smallest Range Covering Element from K Lists | Find the smallest range in k lists covering all elements. | Link | Non |
16 | Find Median in a Stream | Compute the median dynamically in a stream of numbers. | Non | Link |
17 | Find Median From Data Stream | Calculate the median from a continuous data stream. | Link | Non |
Happy Coding😊