I came across a **python beginner** tutorial that mentioned *heapq* and *heapify*. Because I never heard of those guys before and because like I said it was part of a beginner tutorial I decided to look into those and here is what I learned.

Let’s suppose you have a list of simple numbers, strings or even dictionaries, you want to find the **N** **smallest** or **largest** elements from that list, **heapq** is your friend in this case.

```
>>> import heapq
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heapq.nsmallest(3, nums)
[-4, 1, 2]
>>> heapq.nlargest(2, nums)
[42, 37]
```

But this also works with a more complicated data structure such as dictionaries

```
>>> portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
>>> cheap = heapq.smallest(3, portfolio, key=lambda s: s['price'])
>>> cheap
[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
```

In the case of a simple search where the number of elements to retrieve is small compare to the number of elements in the list, use **heapify**

```
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heap = list(nums)
>>> heapq.heapify(heap)
>>> heapq[0:2]
[-4, 1]
```

It’s also possible to use **heappop** to find one by one the smallest elements. This operation is a **O(logN)** operation.

To find the 3 smallest numbers for example

```
>>> heapq.heappop(heap)
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
```

Other solution to retrieve the min and max are

- using
**min()**and**max()** **sorted(items)[:N]**or**sorted(items)[-N:]**

## heappush, heappop

**heappush** provides a way to “sort” or “prioritize” the elements by giving it a 2-elements tuple where the first arguments is the priority key and the second the item itself. Here is in action.

```
import heapq
class PriorityQueue(object):
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
```

```
class Item(object):
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
```

```
>>> q = PriorityQueue()
>>> q.push(Item("Barcelona"), 1)
>>> q.push(Item("Manchester"), 4)
>>> q.push(Item("PSG"), 10)
>>> q.push(Item("LA Galaxy"), 0)
>>> q.pop()
Item('PSG')
>>> q.pop()
Item('Manchester')
```

It’s important to notice that the **push** and **pop** operations have a O(logN) complexity (N is the number of items in the heap) so they are fairly efficient.