# Heaps Flashcards

min heap

min at top. parent node value <= value of the child nodes.

min heap is the default in python

heap insertion time complexity

worst case O(log n)

heap delete node time complexity

worst case O(log n)

heap lib in python

heapq which is short for heap queue which is also an implementation of priority queue. MIN heap.

solution to kth largest element

import heapq heapq.nlargest(k, nums)[-1]

nlargest returns items in descending order (even though heapq is a MIN heap). return k items then take the tail.

Tell me about heaps

- Mainly used to represent a priority queue
- Heaps are complete binary trees (all the levels are completely filled except possibly the lowest one which is filled from left to right)

Representing a heap as an array

Use level ordering to complete the array

Max heap

the parent node value >= value of the child node

How do you convert a heap into an array?

Use level order

Return parent node of heap array

a[ (i-1) // 2 ]

Return left child node of heap array

a[ 2i + 1 ]

Return right child node of heap array

a[ 2i + 2 ]

convert array heap to tree struct

import heapq as hq

hq.heapify(array)

add item to heap tree

import heapq as hq

heappush

remove item from heap tree

import heapq as hq

heappop

throws exception if heap is empty