Python实现MinHeap/MaxHeap：如何添加O(1)时间复杂度的peek方法？

Hey there! Great job getting your MinHeap and MaxHeap implementations off the ground. That pop-and-reinsert workaround for peek works, but as you’ve guessed, there’s a far more efficient way to get that O(1) peek functionality you’re after—let’s break it down.

Why Pop-and-Reinsert Isn’t Ideal #

First, let’s clarify why your current approach isn’t optimal:

• Popping the top element requires O(log n) time to re-heapify the structure.
• Re-inserting that element adds another O(log n) operation.
• Total time complexity here is O(log n), which is unnecessary when we can do better.

The O(1) Solution: Directly Access the Heap Top #

Heaps are typically implemented using arrays, and their core property makes this easy:

• For a MinHeap, the smallest element is always at the first index (heap[0] in 0-based indexing).
• For a MaxHeap, the largest element is also always at heap[0].

Since peek only requires viewing the top element without modifying the heap, we can simply return this index directly—no heapifying required, hence O(1) time.

Example Implementations #

Here’s how to add the peek method to your existing heap classes:

MinHeap with O(1) Peek

class MinHeap:
    def __init__(self):
        self.heap = []

    def _heapify_up(self, index):
        parent_idx = (index - 1) // 2
        while index > 0 and self.heap[index] < self.heap[parent_idx]:
            self.heap[index], self.heap[parent_idx] = self.heap[parent_idx], self.heap[index]
            index = parent_idx
            parent_idx = (index - 1) // 2

    def _heapify_down(self, index):
        n = len(self.heap)
        while True:
            left_child_idx = 2 * index + 1
            right_child_idx = 2 * index + 2
            smallest = index

            if left_child_idx < n and self.heap[left_child_idx] < self.heap[smallest]:
                smallest = left_child_idx
            if right_child_idx < n and self.heap[right_child_idx] < self.heap[smallest]:
                smallest = right_child_idx

            if smallest != index:
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest
            else:
                break

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("Cannot pop from empty MinHeap")
        # Swap top and last element to maintain heap structure
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        min_val = self.heap.pop()
        self._heapify_down(0)
        return min_val

    # O(1) peek method
    def peek(self):
        if not self.heap:
            raise IndexError("Cannot peek into empty MinHeap")
        return self.heap[0]

MaxHeap with O(1) Peek

The logic is identical for MaxHeap—only the heapify comparisons are reversed, and peek still returns heap[0]:

class MaxHeap:
    def __init__(self):
        self.heap = []

    def _heapify_up(self, index):
        parent_idx = (index - 1) // 2
        while index > 0 and self.heap[index] > self.heap[parent_idx]:
            self.heap[index], self.heap[parent_idx] = self.heap[parent_idx], self.heap[index]
            index = parent_idx
            parent_idx = (index - 1) // 2

    def _heapify_down(self, index):
        n = len(self.heap)
        while True:
            left_child_idx = 2 * index + 1
            right_child_idx = 2 * index + 2
            largest = index

            if left_child_idx < n and self.heap[left_child_idx] > self.heap[largest]:
                largest = left_child_idx
            if right_child_idx < n and self.heap[right_child_idx] > self.heap[largest]:
                largest = right_child_idx

            if largest != index:
                self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
                index = largest
            else:
                break

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            raise IndexError("Cannot pop from empty MaxHeap")
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        max_val = self.heap.pop()
        self._heapify_down(0)
        return max_val

    # O(1) peek method
    def peek(self):
        if not self.heap:
            raise IndexError("Cannot peek into empty MaxHeap")
        return self.heap[0]

Key Notes #

• Handle Empty Heaps: Always add a check for an empty heap in your peek method to avoid IndexError when accessing heap[0].
• No Structural Changes: Unlike pop-and-reinsert, this peek method leaves the heap completely unchanged—perfect for use cases where you just need to inspect the top element.

Give this implementation a spin, and you’ll have that efficient O(1) peek working seamlessly with your heaps. If you need to adjust anything for your specific use case, feel free to tweak the error handling or add edge case checks as needed!

内容的提问来源于stack exchange，提问作者Melissa Stewart