Feature or enhancement

Proposal: adding a new data structure called HeapDict to the Python collections module

Description

I would like to propose adding a new data structure called HeapDict to the Python collections module. This data structure would combine the functionality of a dictionary with a heap, providing efficient access to key-value pairs while maintaining a heap property for priority-based operations.

Motivation

Currently, Python offers heapq for heap operations and dictionaries for key-value storage, but there's no built-in data structure that efficiently combines both functionalities. A HeapDict would be useful in many scenarios:

• Priority queues where items need to be accessed by key
• Caching mechanisms with priority-based eviction
• Algorithms requiring both random access and priority-based operations (e.g., Dijkstra's algorithm)
• Task schedulers with dynamic priority updates

Proposed API

class HeapDict(collections.abc.MutableMapping):
    """Dictionary that maintains heap property based on values."""

    def __init__(self, *args, **kwargs):
        """Initialize a new HeapDict with optional initial values."""

    def popmin(self):
        """Remove and return the (key, value) pair with minimum value."""

    def peekmin(self):
        """Return the (key, value) pair with minimum value without removing it."""

    def update_priority(self, key, new_value):
        """Update the value/priority of an existing key."""

Implementation Considerations

• The implementation would likely use a combination of a dictionary for O(1) key lookups and a heap for maintaining the priority order
• Special attention would be needed for handling duplicate priorities
• The implementation should ensure that all operations maintain both the dictionary and heap properties efficiently

Related Work

• Python's heapq module provides heap operations but doesn't support key-based access
• Third-party packages like heapdict and prioritydict exist but aren't part of the standard library
• Other languages have similar structures (e.g., Java's PriorityQueue with custom comparators)

Has this already been discussed elsewhere?

No response given

Links to previous discussion of this feature:

No response

Linked PRs

• gh-136898: feat(collections)-Add HeapDict class #136900