# Sorted data structure in the stdlib?

**URL:** <https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994>\
**Category:** Ideas\
**Created:** [July 2, 2026, 4:01pm UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994 "2026-07-02T16:01:51Z")\
**Posts on this page:** 1\
**Showing post:** 30

<div class="post-metadata">

**Author:** ![tim.one](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/tim.one/32/282_2.png) [@tim.one](https://discuss.python.org/u/tim.one)\
**Post date:** [July 8, 2026, 4:31am UTC](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994/30 "2026-07-08T04:31:04Z")

</div>

> [@dg-pb](#):
>
> And minmax heap is a long shot here… Would be quite fancy improvement ofc, especially if it is faster than `heapq`. But I imagine new heap is very far down the priority list.

I don’t think there is a “priority list” here 😉.Only very trendy things get added now in the absence of very compelling real-life use cases.

In the general area of priority queues, the most frequent annoyance I’ve encountered is the lack of a pleasant approach to the “decrease key” primitive. For example. you’ re using A\* to find an optimal (“lowest cost”) path between two sets of points in a state space, implemented as some form of weighted graph.

Ai it it goes on, a particular node can be encountered more than once, via different paths from the start set. Then some successor of the current-lowest state may already be on the queue. What to do? If a lower bound on a completion is smaller than the lower bound computed for the completion of the path found before. we don’t want to add the state redundantly - we want to _decrease_ the lower bound for this state saved before. “Decrease key”.

Now an underlying priority queue implementation may well support this functionality very efficiently. For example, for a plain list arranged as a heap, simply swap the old heap node with its parent so long as the new lower bound is smaller than the parent’s. At the worst at most \log\_2{n} swaps.

BUT! We don’t know where the earlier instance of the node lived in the heap, and there’s no efficient way to find it.

A fancier implementation can store the heap index in each heap entry, and keep it updated as heap nodes change position. Then we need also to add a way to find a heap node (if any) given a state’s value (not just some path \_to\_the state).

It can get quite involved, and there appears to be plausible way for a generic “priority queue class” to supply everything that’s needed. Some other approaches (all of which I’ve tiried, none of which I liked):☹ .

- Write a custom prioirihy queue that supplies exactly what its client really needs.

- Rewrite the simple heap-as-plain-list code to keep track of elements’ indices, storing them in element instances. A client using this code needs to define an element class that inherits from a specific mixin class (which supplies an instance attribute to store the element’s index).

- Punt! Store duplicate states redundantly,. This is a more-general meta approach that can also apply to other priority queue headaches. Rather than try to avoid adding useless entries, instead craft a way to _identify_ than as redundant if/when they’re popped. So start the search loop like so:

```py
    while heap:
        state = heap.pop()
        if state.is_useless():
            continue
       if state.is_goal():
           return state
       for each successor state:
            compute lower bound on completion and push

```

There typically aren’t oodles of useless states added, and heap operations are log time, so speed can actually be better than with “look before you leap” (which requires slowing every mutating operation to keep indices updated). And no changes to the priority code in use are needed - no “decrease minimum” function is asked for.,

Which is all a long-winded say of saying the real world is more complicated than our clean abstractions hope for 😉.

---

_[View the full topic](https://discuss.python.org/t/sorted-data-structure-in-the-stdlib/107994)._