heapq – Heap Sort Algorithm — PyMOTW 3
A heap is a tree-like data structure where the child nodes have a sort-order relationship with the parents. Binary heaps can be represented using a list or array organized so that the children of element N are at positions 2*N+1 and 2*N+2 (for zero-based indexes). This layout makes it possible to rearrange heaps in place, so it is not necessary to reallocate as much memory when adding or removing items.
This post is part of the Python Module of the Week series for Python 3. See PyMOTW.com for more articles from the series.