# Heaps Flashcards

1
Q

min heap

A

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

min heap is the default in python

2
Q

heap insertion time complexity

A

worst case O(log n)

3
Q

heap delete node time complexity

A

worst case O(log n)

4
Q

heap lib in python

A

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

5
Q

solution to kth largest element

A

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.

6
Q

A
• 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)
7
Q

Representing a heap as an array

A

Use level ordering to complete the array

8
Q

Max heap

A

the parent node value >= value of the child node

9
Q

How do you convert a heap into an array?

A

Use level order

10
Q

Return parent node of heap array

A

a[ (i-1) // 2 ]

11
Q

Return left child node of heap array

A

a[ 2i + 1 ]

12
Q

Return right child node of heap array

A

a[ 2i + 2 ]

13
Q

convert array heap to tree struct

A

import heapq as hq
hq.heapify(array)

14
Q

A

import heapq as hq
heappush

15
Q

remove item from heap tree

A

import heapq as hq
heappop
throws exception if heap is empty

16
Q

getMin/getMax time complexity

A

O(1)

17
Q

heapify time complexity

A

O(n)