> For the complete documentation index, see [llms.txt](https://lintcode-solutions.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lintcode-solutions.gitbook.io/project/cs-fundamentals/python/heap.md).

# Heap

## `heapq`

implementation of the **heap queue** algorithm, also known as the **priority queue** algorithm

### `heapq.heappush`(*heap*, *item*)

Push the value *item* onto the *heap*, maintaining the heap invariant.`heapq.heappop`(*heap*)

Pop and return the smallest item from the *heap*, maintaining the heap invariant. If the heap is empty, [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError) is raised. To access the smallest item without popping it, use `heap[0]`.

### `heapq.heappushpop`(*heap*, *item*)

Push *item* on the heap, then pop and return the smallest item from the *heap*. The combined action runs more efficiently than [`heappush()`](https://docs.python.org/2/library/heapq.html#heapq.heappush)followed by a separate call to [`heappop()`](https://docs.python.org/2/library/heapq.html#heapq.heappop).

### `heapq.heapify`(*x*)

Transform list *x* into a heap, in-place, in **linear** time.

### `heapq.heapreplace`(*heap*, *item*)

Pop and return the smallest item from the *heap*, and also push the new *item*. The heap size doesn’t change. If the heap is empty, [`IndexError`](https://docs.python.org/2/library/exceptions.html#exceptions.IndexError) is raised.

### `heapq.nlargest`(*n*, *iterable*\[, *key*])

Return a list with the *`n`* largest elements from the dataset defined by *iterable*. *key*, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: `key=str.lower` Equivalent to: `sorted(iterable, key=key, reverse=True)[:n]`

### `heapq.nsmallest`(*n*, *iterable*\[, *key*])

Return a list with the *`n`* smallest elements from the dataset defined by *iterable*. *key*, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: `key=str.lower` Equivalent to: `sorted(iterable, key=key)[:n]`