## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 5.7. Keeping a Sequence Ordered as Items Are Added

Credit: John Nielsen

## Problem

You want to maintain a sequence, to which items are added, in a sorted state, so that at any time, you can easily examine or remove the smallest item currently present in the sequence.

## Solution

Say you start with an unordered list, such as:

`the_list = [903, 10, 35, 69, 933, 485, 519, 379, 102, 402, 883, 1]`

You could call ```the_list.sort( )``` to make the list sorted and then `result=the_list.pop(0)` to get and remove the smallest item. But then, every time you add an item (say with `the_list.append(0)`), you need to call `the_list.sort( )` again to keep the list sorted.

Alternatively, you can use the `heapq` module of the Python Standard Library:

```import heapq
heapq.heapify(the_list)```

Now the list is not necessarily fully sorted, but it does satisfy the heap property (meaning if all indices involved are valid, `the_list[i]<=the_list[2*i+1]` and `the_list[i]<=the_list[2*i+2]`)—so, in particular, `the_list[0]` is the smallest item. To keep the heap property valid, use `result=heapq.heappop(the_list)` to get and remove the smallest item and `heapq.heappush(the_list, newitem)` to add a new item. When you need to do both—add a new item while getting and removing the previously smallest item—you can use `result=heapq.heapreplace(the_list`, `newitem)`.

## Discussion

When you need to retrieve data in an ordered way (at each retrieval getting the smallest item among those you currently have at hand), you can pay the runtime cost for the sorting when ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required