O'Reilly logo

Python Cookbook, 2nd Edition by David Ascher, Anna Ravenscroft, Alex Martelli

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required