Table of Content

1. Introduction to Heaps

• Problem Context:
  • You’re developing a food delivery application called "Quick Dash," where you need to manage discount coupons efficiently.
  • The goal is to ensure the best discount coupon is always easily accessible.
  • Simple sorting of coupons in a list is inefficient (O(N log N) time complexity).
• Initial Solution with Linked List:
  • Linked lists improve some aspects but still face inefficiencies in insertion, deletion, and retrieval operations.
• Introducing Heaps:
  • Heap Basics: Heaps are specialized tree-based data structures used to efficiently manage and retrieve elements based on priority.
  • Types of Heaps:
    • Min-Heap: The smallest element is always at the top.
    • Max-Heap: The largest element is always at the top.
  • Binary Heap:
    • A complete binary tree where all levels are fully filled, except possibly the last level, filled from left to right.
    • Min-Heap Property: Each node's value is greater than or equal to its parent.
    • Max-Heap Property: Each node's value is less than or equal to its parent.
    • Array Representation: Binary heaps are typically stored in arrays for efficient access.
    • Parent-Child Relationships: Calculations for finding left/right child and parent indices based on the current index.

2. Operations on Heaps

• Inserting Elements (Min-Heap Focus):
  • Shift-Up Operation: Ensures the heap property is maintained after inserting a new element. The element is shifted up until it is correctly positioned.
  • Time Complexity: O(log N) for insertion; O(1) for space complexity.
• Updating Elements:
  • Shift-Up and Shift-Down Operations:
    • Shift-Up: Used when the new value is smaller than the old value.
    • Shift-Down: Used when the new value is larger than the old value.
  • Two Scenarios:
    • If the index of the element is known: O(log N) time complexity.
    • If the index is unknown: O(N) time for searching + O(log N) for updating.
• Extracting Minimum/Maximum:
  • Min-Heap Extraction:
    • Replace the root with the last element.
    • Remove the last element.
    • Apply the Shift-Down operation to maintain the heap structure.
  • Time Complexity: O(log N) for extraction.
• Building a Heap:
  • Naive Approach: Insert each element one by one into an empty heap—O(N log N) time.
  • Optimal Approach: Start from the last node and perform sift-down for each node up to the root—O(N) time.

3. Heap Sort

• Overview:
  • Heap Sort leverages the properties of heaps to sort elements efficiently.
  • Involves three phases: building the heap, extracting elements, and saving them in a new array.
• Steps in Heap Sort:
  • Build the Heap:
    • For ascending order, build a min-heap.
    • Start from the last non-leaf node and apply sift-down operations.
  • Extract and Save Elements:
    • Continuously extract the minimum element and save it to a new list.
    • Repeat until the heap is empty.
• Time and Space Complexity:
  • Time Complexity: O(N log N) for both average and worst-case scenarios.
  • Space Complexity: O(N) for storing the sorted array.

4. Priority Queue in Java

• Priority Queue Overview:
  • A special type of queue that manages data with priority ordering.
  • Key Characteristics:
    • Elements are ordered based on their priority.
    • Dynamic sizing and heap-based implementation for efficiency.