The best() Operation - O(1) Access to Root

The best() operation is the simplest yet most important operation in a priority queue. It returns the highest-priority item without modifying the heap.

Why best() Is So Simple

Recall the heap order property from Day 41: In a max-heap, every parent is greater than or equal to its children. This means the maximum value is always at the root.

Since we store the heap in an array with the root at index 0, accessing the highest-priority item is trivial:

public T best() {
    if (isEmpty()) {
        throw new EmptyPriorityQueueException("Cannot access best from empty priority queue");
    }
    return heap[0];  // Root is always at index 0
}

That's it! No searching, no comparisons, no traversal—just return the first element.

Visual Example

Max-Heap:
        [90]
       /    \
      /      \
    [75]    [80]
   /   \   /   \
  /     \ /     \
[50]  [60][70] [40]

Array representation:
Index: 0    1    2    3    4    5    6
      [90] [75] [80] [50] [60] [70] [40]
       ↑
    best() returns this value

No searching needed - always at index 0!

Why This Is O(1)

Time complexity: O(1) - constant time

• No loop or recursion
• Single array access
• No comparisons with other elements
• Independent of heap size n

Comparison with alternatives from Day 41:

• Unsorted array: O(n) - must scan entire array to find maximum
• Sorted array: O(1) - maximum at end, but insert is O(n)
• Unsorted list: O(n) - must traverse entire list
• Binary heap: O(1) - maximum always at root ✓

Edge Case: Empty Heap

What if we call best() on an empty heap?

Strategy: Throw an exception—this is a precondition violation.

if (isEmpty()) {
    throw new EmptyPriorityQueueException("Cannot access best from empty priority queue");
}

Why throw an exception? There's no sensible value to return. Returning null would force every caller to check for null, and the heap might contain null values (if allowed). An exception makes the precondition violation explicit.

best() vs remove()

Critical distinction: best() only observes the highest-priority item—it doesn't modify the heap.

// Repeated calls to best() return the same value
pq.best();  // Returns 90
pq.best();  // Still returns 90
pq.best();  // Still returns 90

// remove() both returns AND modifies
pq.remove();  // Returns 90 (and removes it)
pq.best();    // Now returns 75 (new maximum)

Use case for best(): Checking priority without committing to processing the item yet.

Example - Task Scheduler:

// Peek at the highest-priority task
Task nextTask = scheduler.best();

if (canProcessNow(nextTask)) {
    // OK to process, actually remove it
    scheduler.remove();
    process(nextTask);
} else {
    // Can't process yet, leave it in the queue
    // (best() didn't modify the queue)
}

Implementation Variations

Alternative names for best():

• peek() - Java's PriorityQueue uses this name
• top() - common in competitive programming
• findMax() or findMin() - emphasizes max vs min heap
• front() - less common, but draws parallel to queue's front()

All refer to the same O(1) operation: accessing the root without removal.

Summary

The best() operation showcases the elegance of the heap structure:

• O(1) time - just return heap[0]
• No side effects - heap remains unchanged
• Simple implementation - two lines of code
• Always correct - heap property guarantees root is maximum

This simplicity is only possible because the heap property ensures the maximum lives at a known location. On the next page, we'll see how insert() maintains this property when adding new elements.