Feature or enhancement
Proposal:
Add two classes, MinHeap and MaxHeap, to the heapq module, providing an object-oriented interface on top of the existing functions.
Today heapq exposes only module-level functions that operate on a bare list that the caller has to create and pass around on every call:
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
smallest = heapq.heappop(heap)
This works, but it is easy to misuse: nothing ties the list to the heap invariant, an ordinary list method can silently break it, and the caller must remember to always go through heapq. An object that owns its data and exposes the operations as methods is a more natural, discoverable interface:
from heapq import MinHeap
heap = MinHeap([3, 1, 2])
heap.push(0)
smallest = heap.pop()
Proposed API: Two classes that share the same interface (only the direction of the ordering differs):
MinHeap(iterable=None) / MaxHeap(iterable=None): create a heap, optionally initialized from an iterablepush(item) / pop() / etc.: mimic the interface of the module's functions__len__, __bool__, __repr__: special methods to make the object Pythonic
Has this already been discussed elsewhere?
I have already discussed this feature proposal on Discourse
Links to previous discussion of this feature:
The idea of an object-oriented wrapper for heapq was originally proposed on python-ideas back in 2009. At the time the module only offered a min-heap, but the idea is extensible. The topic came up again recently on Discuss, in the context of sorted priority-queue data structures in the standard library.
Linked PRs
Feature or enhancement
Proposal:
Add two classes,
MinHeapandMaxHeap, to theheapqmodule, providing an object-oriented interface on top of the existing functions.Today
heapqexposes only module-level functions that operate on a barelistthat the caller has to create and pass around on every call:This works, but it is easy to misuse: nothing ties the list to the heap invariant, an ordinary list method can silently break it, and the caller must remember to always go through heapq. An object that owns its data and exposes the operations as methods is a more natural, discoverable interface:
Proposed API: Two classes that share the same interface (only the direction of the ordering differs):
MinHeap(iterable=None)/MaxHeap(iterable=None): create a heap, optionally initialized from an iterablepush(item)/pop()/ etc.: mimic the interface of the module's functions__len__,__bool__,__repr__: special methods to make the object PythonicHas this already been discussed elsewhere?
I have already discussed this feature proposal on Discourse
Links to previous discussion of this feature:
The idea of an object-oriented wrapper for heapq was originally proposed on python-ideas back in 2009. At the time the module only offered a min-heap, but the idea is extensible. The topic came up again recently on Discuss, in the context of sorted priority-queue data structures in the standard library.
Linked PRs