Heaps

Heaps in Java

Heaps are a fundamental data structure in Java and are widely used in Leetcode problems. A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, the parent node is always smaller than or equal to its children, and in a max-heap, the parent node is always larger than or equal to its children.

Table of Contents

1. Heap Basics
2. Common Heap Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

Heap Basics

• Definition: A heap is a complete binary tree that satisfies the heap property:

  • Min-Heap: The parent node is always smaller than or equal to its children.
  • Max-Heap: The parent node is always larger than or equal to its children.

• Declaration:

  // Min-Heap
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  
  // Max-Heap
  PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

• Key Characteristics:

  • Complete binary tree.
  • Efficient for finding the minimum or maximum element in O(1) time.
  • Commonly implemented using PriorityQueue in Java.

Common Heap Operations

1. Inserting an Element

• Method: add(E e) or offer(E e)
• Example:

  minHeap.add(5);
  minHeap.offer(3);

• Time Complexity: O(log n)
• Space Complexity: O(1)

2. Removing the Top Element

• Method: poll()
• Example:

  int topElement = minHeap.poll(); // Removes and returns the top element

• Time Complexity: O(log n)
• Space Complexity: O(1)

3. Peeking at the Top Element

• Method: peek()
• Example:

  int topElement = minHeap.peek(); // Returns the top element without removing it

• Time Complexity: O(1)
• Space Complexity: O(1)

4. Checking if the Heap is Empty

• Method: isEmpty()
• Example:

  boolean isEmpty = minHeap.isEmpty(); // isEmpty = false

• Time Complexity: O(1)
• Space Complexity: O(1)

5. Size of the Heap

• Method: size()
• Example:

  int size = minHeap.size(); // size = 2

• Time Complexity: O(1)
• Space Complexity: O(1)

Common Leetcode Patterns

1. Finding the Kth Largest/Smallest Element

• Used for problems like Kth largest element in an array, Kth smallest element in a stream, etc.
• Example:

  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int num : nums) {
      minHeap.add(num);
      if (minHeap.size() > k) {
          minHeap.poll();
      }
  }
  return minHeap.peek();

• Related Questions:
  • Kth Largest Element in an Array
  • Kth Smallest Element in a Sorted Matrix
  • Kth Largest Element in a Stream

2. Merge K Sorted Lists

• Used for problems like merging K sorted lists, finding the median of sorted arrays, etc.
• Example:

  PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
  for (ListNode node : lists) {
      if (node != null) {
          minHeap.add(node);
      }
  }
  ListNode dummy = new ListNode(0);
  ListNode current = dummy;
  while (!minHeap.isEmpty()) {
      ListNode node = minHeap.poll();
      current.next = node;
      current = current.next;
      if (node.next != null) {
          minHeap.add(node.next);
      }
  }
  return dummy.next;

• Related Questions:
  • Merge k Sorted Lists
  • Find Median from Data Stream

3. Top K Frequent Elements

• Used for problems like finding the top K frequent elements, sorting characters by frequency, etc.
• Example:

  Map<Integer, Integer> frequencyMap = new HashMap<>();
  for (int num : nums) {
      frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
  }
  PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
      (a, b) -> a.getValue() - b.getValue()
  );
  for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
      minHeap.add(entry);
      if (minHeap.size() > k) {
          minHeap.poll();
      }
  }
  int[] result = new int[k];
  for (int i = 0; i < k; i++) {
      result[i] = minHeap.poll().getKey();
  }
  return result;

• Related Questions:
  • Top K Frequent Elements
  • Sort Characters By Frequency

4. Sliding Window Median

• Used for problems like finding the median in a sliding window, sliding window maximum, etc.
• Example:

  PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int i = 0; i < nums.length; i++) {
      maxHeap.add(nums[i]);
      minHeap.add(maxHeap.poll());
      if (maxHeap.size() < minHeap.size()) {
          maxHeap.add(minHeap.poll());
      }
      if (i >= k - 1) {
          if (maxHeap.size() > minHeap.size()) {
              result[i - k + 1] = maxHeap.peek();
          } else {
              result[i - k + 1] = (maxHeap.peek() + minHeap.peek()) / 2.0;
          }
          int numToRemove = nums[i - k + 1];
          if (numToRemove <= maxHeap.peek()) {
              maxHeap.remove(numToRemove);
          } else {
              minHeap.remove(numToRemove);
          }
      }
  }
  return result;

• Related Questions:
  • Sliding Window Median
  • Sliding Window Maximum

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insert (add(), offer())	O(log n)	O(1)
Remove (poll())	O(log n)	O(1)
Peek (peek())	O(1)	O(1)
Is Empty (isEmpty())	O(1)	O(1)
Size (size())	O(1)	O(1)

Related Leetcode Questions

Easy

1. Kth Largest Element in an Array
2. Top K Frequent Elements
3. Sort Characters By Frequency

Medium

1. Merge k Sorted Lists
2. Find Median from Data Stream
3. Sliding Window Median

Hard

1. Kth Smallest Element in a Sorted Matrix
2. Sliding Window Maximum
3. Reorganize String