# Heap Data Structure

A

**heap**is a tree-based data structure that maintains properties such that either the maximum or minimum value from a set can be retrieved efficiently.The two types of heaps are:

**Min heap**- The root node of each subtree is the*smallest*element.**Max heap**- The root node of each subtree is the*largest*element.

A heap is a

**complete binary tree**, which means all the levels in the tree are*filled*(have both left and right nodes), except the last level.## Heap Operations

The 4 main operations of a heap are:

**Get min**- Get the root element of the heap (the max element in the case of a max heap)**Push**- Add an element to the heap. Newly added nodes are placed in the next available position in the tree to maintain its completeness. The node is then swapped with its parent until it is smaller than its children, and the heap property is maintained.**Pop**- Remove and retrieve the root element of the heap (the*smallest*element in a*min heap*, the*largest*in a*max heap*). The heap is reorganized such that the next smallest number becomes the root, maintaining the heap property.**Heapify**- Convert an*iterable*(a list for example) into a heap by reordering the elements.

## Heap Big O

Both min and max heaps have the same time complexity. So let's take a look at a

**min heap**Big O:Operation | Worst Case Time |
---|---|

Insert | O(log n) |

Pop | O(log n) |

Push | O(log n) |

Get min | O(1) |

## Heap Implementation

In

*Python*, the best way to use a heap is the`heapq`

module.### Heapify

If you want to convert an

*iterable*to a*heap*:### Pop

To pop the smallest number off the heap, we can use

`heappop()`

### Push

We can add a new person's age to our heap with

`heappush()`

### Get min

If we want to just retrieve the smallest number without popping it off, the root is in the first position of a heapified iterable:

### Max heap

Python's

`heapq`

operates as a **min heap**under the hood. To use a**max heap**, simply negate the values before they enter the heap.And remember to

*negate again*when reading from the max heap.## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard