# Heap

Heaps have special properties that make it perfect for solving problems involving finding the min or max of something:

- It will always give you either its
**largest**or**smallest**element - It takes
**O(log(n))**time to add an item to a heap - It takes
**O(1)**time to remove the top element in a heap

Examples of questions that we could use heaps to solve are: find the shortest distance between two nodes in a weighted graph, keep track of the n largest digits.

## Creating a heap

In Python, the two popular ways to create a heap is via either a

or **PriorityQueue**

. The difference between them is **heapq**`heapq`

is a library that performs functions on a heap (which is a list), while PriorityQueue is a pre-built class.

We'll use

for these two reasons:**heapq**

`heapq`

allows you to start the heap with existing items`heapq`

allows you to print out the entire heap

#### Note

also tends to be a little faster because it is not threadsafe. However, interviewers **heapq****do not** care if you pick a fast library or not, so just use your favorite.

Our heap can simply be represented with an empty list:

Or we can initialized the list with existing items, and then use `heapify()`

to rearrange the list into the heap:

#### Note

`heapify()`

**does not** sort the heap, it only ensures the first/top-most item is the smallest item. `heapify()`

also takes **O(n)** time to arrange all the items in the heap.

If the items in the heap are tuples, `heapify()`

use the first value in the tuple to arrange by:

## Adding an item to the heap

O(log(n))Add an item to the heap via the

function:**heappush()**

## Removing an item from the heap

O(log(n))To remove an item from a heap, use

. This returns the item with the lowest value in the heap:**heappop()**

## Getting an item from the heap

O(1)Since the heap is a list, you can look at index 0 of the list to peek at the smallest value in the heap:

## Tips and tricks #1

If you want to create a max heap (a heap that will return the maximum value), use a negative priority.

## Tips and tricks #2

If tuples are stored in the heap, `heapq`

will attempt to arrange the items based on the first values of the tuples, and then the second values if the first values are equivalent. This is especially helpful to keep in mind when when you need to store extra data for solutions, like finding the shortest path in a weighted graph.