This section covers the heap data structure and various sorting algorithms.
A heap is a specialized tree-based data structure that satisfies the heap property. In Java, heaps are implemented by the PriorityQueue class.
- By default,
PriorityQueueis a min-heap: the head of the queue is the smallest element. - To create a max-heap, you must provide a custom
Comparator.
| Operation | Time Complexity |
|---|---|
| Insert (offer) | O(log n) |
| Delete Min/Max (poll) | O(log n) |
| Peek Min/Max (peek) | O(1) |
Heaps are useful for:
- Finding the min/max element in a collection efficiently.
- Problems involving scheduling or task prioritization.
- "Top K" problems (e.g., find the k-th largest/smallest element).
This pattern uses a min-heap to keep track of the k largest elements seen so far.
import java.util.PriorityQueue;
class Solution {
public int findKthLargest(int[] nums, int k) {
// Use a min-heap to store the k largest elements.
// The smallest of these k elements will be at the top of the heap.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove the smallest element if the heap size exceeds k
}
}
return minHeap.peek();
}
}Example Problem: Kth Largest Element in an Array
(Solution file KthLargestElement.java is in this directory)
Sorting is the process of arranging items in a certain sequence.
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Notes |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Simple but inefficient. |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Inefficient, but makes minimal swaps. |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Efficient for nearly sorted data. |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable sort, good for external sorting. |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | Fast in practice, but worst case is O(n^2). Not stable. |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place, but not stable. |
Java's Arrays.sort() uses a dual-pivot QuickSort for primitive types and MergeSort (or TimSort) for objects.