Skip to content

Max-heaps and heap tie breakers [ref]

Problem

  • Represent [3, 7, 5] as a max-heap by negating its values.
  • Push 8 and pop the maximum from that heap.
  • Push two unorderable nodes with equal priority using unique integer tie breakers.
  • Compare tuples whose first fields tie but second fields differ.

Python solution

import heapq

heap = [-x for x in [3, 7, 5]]
heapq.heapify(heap)
-heap[0]  # 7

heapq.heappush(heap, -8)
-heapq.heappop(heap)  # 8

class Node:
    def __init__(self, value):
        self.value = value

records = []
heapq.heappush(records, (5, 0, Node("a")))
heapq.heappush(records, (5, 1, Node("b")))
priority, tie, node = heapq.heappop(records)
(priority, tie, node.value)  # (5, 0, 'a')

(5, 0, "x") < (5, 1, "a")  # True