Skip to content

Heap push, pop, and replacement [ref]

Problem

  • Heapify [5, 1, 3] and read its minimum.
  • Push 2, then pop the minimum.
  • Replace the minimum with 4 in one operation.
  • Find the two largest values of [5, 1, 3, 9].
  • Maintain the three largest values in [8, 2, 6, 10, 4] using a min-heap.

Python solution

import heapq

heap = [5, 1, 3]
heapq.heapify(heap)
heap[0]  # 1

heapq.heappush(heap, 2)
heapq.heappop(heap)  # 1
heap  # [2, 5, 3]

heapq.heapreplace(heap, 4)  # 2
heap[0]  # 3

heapq.nlargest(2, [5, 1, 3, 9])  # [9, 5]

heap = []
for x in [8, 2, 6, 10, 4]:
    if len(heap) < 3:
        heapq.heappush(heap, x)
    elif x > heap[0]:
        heapq.heapreplace(heap, x)
sorted(heap)  # [6, 8, 10]