Problem Context: In the "Quick Dash" food delivery app, managing discount coupons efficiently requires quick access to the best offer. Sorting coupons in a list is inefficient (O(N log N)).
Linked List Limitations: Linked lists improve some aspects but still have inefficient insertion, deletion, and retrieval.
Introducing Heaps:
Heap Basics: Heaps are tree-based structures that efficiently manage elements by priority.
Types of Heaps:
Min-Heap: Smallest element at the top.
Max-Heap: Largest element at the top.
Binary Heap:
A complete binary tree stored in an array.
Min-Heap Property: Parent is smaller than children.
Max-Heap Property: Parent is larger than children.
Operations on Heaps
Inserting Elements (Min-Heap Focus):
Shift-Up: Adjusts position of a new element to maintain heap property.
Time Complexity: O(log N) insertion.
Updating Elements:
Shift-Up for smaller values, Shift-Down for larger values.
Time Complexity: O(log N) if index is known; O(N) for searching + O(log N) for updating.
Extracting Minimum/Maximum:
Replace root with last element, remove it, and apply Shift-Down.
Time Complexity: O(log N).
Building a Heap:
Naive: Insert each element—O(N log N).
Optimal: Sift-down from last node—O(N).
For more detailed information, refer to the Notion link:
