Complexity Analysis

Question 1

Implementation of Binary Search Tree

Answer 1

Children Pointers

Question 2

BST insert

Answer 2

0(n)

Question 3

BST delete

Answer 3

O(n)

Question 4

BST Search

Answer 4

O(n)

Question 5

BST deleteMin

Answer 5

O(n)

Question 6

BST deleteMax

Answer 6

O(n)

Question 7

Building BST using insert

Answer 7

O(n^2)

Question 8

Building optimal BST using dynamic programming algorithm

Answer 8

O(n^3)

Question 9

Implementation of 2-3 Tree

Answer 9

Children/parent pointers

Question 10

2-3 Tree insert

Answer 10

O(lgn)

Question 11

2-3 Tree delete

Answer 11

O(lgn)

Question 12

2-3 Tree search

Answer 12

O(lgn)

Question 13

2-3 Tree findMin

Answer 13

O(lgn)

Question 14

2-3 Tree findMax

Answer 14

O(lgn)

Question 15

2-3 Tree buildTree

Answer 15

O(nlgn)

Question 16

implementation of k-heap

Answer 16

array-based

Question 17

k-heap insert

Answer 17

O(lgn)

Question 18

k-heap general delete

Answer 18

O(n)

Question 19

k-heap general search

Answer 19

O(n)

Question 20

min k-heap deleteMax

Answer 20

O(n)

Question 21

min k-heap deleteMin

Answer 21

O(lgn)

Question 22

max k-heap deleteMax

Answer 22

O(lgn)

Question 23

max k-heap deleteMin

Answer 23

O(n)

Question 24

k-heap top-down build

Answer 24

O(nlgn)

Question 25

k-heap bottom-up build

Answer 25

O(n)

Question 26

k-heap frequent insertions

Answer 26

want larger k

Question 27

k-heap frequent deletions

Answer 27

want smaller k

Question 28

dual-heap insert

Answer 28

O(lgn)

Question 29

dual-heap deleteMin

Answer 29

O(lgn)

Question 30

dual-heap deleteMax

Answer 30

O(lgn)

Question 31

dual-heap findMin

Answer 31

O(1)

Question 32

dual-heap findMax

Answer 32

O(1)

Question 33

dual-heap buildHeap

Answer 33

O(n)

Question 34

implementation of minmax/maxmin heap

Answer 34

sequential array-based with root at A[1]

Question 35

minmax/maxmin heap insert

Answer 35

O(lgn)

Question 36

minmax/maxmin deleteMin

Answer 36

O(lgn)

Question 37

minmax/maxmin deleteMax

Answer 37

O(lgn)

Question 38

minmax/maxmin top-down build

Answer 38

O(nlgn)

Question 39

minmax/maxmin bottom-up build

Answer 39

O(n)

Question 40

minmax/maxmin findMin

Answer 40

O(1)

Question 41

minmax/maxmin findMax

Answer 41

O(1)

Question 42

implementation of leftist heap

Answer 42

children pointers

Question 43

leftist heap concate

Answer 43

O(lgn)

Question 44

leftist heap insert

Answer 44

O(lgn)

Question 45

leftist heap deleteMin (for min leftist)

Answer 45

O(lgn)

Question 46

leftist heap deleteMax (for max leftist)

Answer 46

O(lgn)

Question 47

leftist heap findMin (for min leftist)

Answer 47

O(1)

Question 48

leftist heap findMax( for max leftist)

Answer 48

O(1)

Question 49

leftist heap buildHeap using insert

Answer 49

O(nlgn)

Question 50

implementation of skew heap

Answer 50

children pointers

Question 51

skew heap concate

Answer 51

O(n)

Question 52

skew heap insert

Answer 52

O(n)

Question 53

skew heap deleteMin (for min skew heap)

Answer 53

O(n)

Question 54

skew heap deleteMax (for max skew heap)

Answer 54

O(n)

Question 55

skew heap findMin (for min skew heap)

Answer 55

O(1)

Question 56

skew heap findMax( for max skew heap)

Answer 56

O(1)

Question 57

skew heap buildHeap using insert

Answer 57

O(n^2)

Question 58

implementation of pairing heap

Answer 58

left-child right-sibling pointers

Question 59

pairing heap merge

Answer 59

O(1)

Question 60

pairing heap insert

Answer 60

O(1)

Question 61

pairing heap findMin (for min pairing heap)

Answer 61

O(1)

Question 62

pairing heap findMax (for max pairing heap)

Answer 62

O(1)

Question 63

pairing heap deleteMin (for min pairing heap)

Answer 63

O(n)

Question 64

pairing heap deleteMax (for max pairing heap)

Answer 64

O(n)

Question 65

pairing heap buildHeap using insert

Answer 65

O(n)

Question 66

What structure(s) are search trees?

Answer 66

binary search trees

2-3 trees

Question 67

What structure(s) are priority queues?

Answer 67

k-heaps

Question 68

What structure(s) are double-ended priority queues?

Answer 68

dual-heaps

minmax/maxmin heaps

Question 69

What structure(s) are concatenated queues?

Answer 69

leftist heaps
skew heaps
pairing heaps

Question 70

Binomial Queue concate

Answer 70

O(lgn)

Question 71

Binomial Queue insert

Answer 71

O(lgn)

Question 72

Binomial Queue deleteMin

Answer 72

O(lgn)

Question 73

Binomial Queue findMin

Answer 73

O(lgn)

Question 74

Binomial Queue Build

Answer 74

O(nlgn)

Question 75

Fibonacci Heap concate

Answer 75

O(1)

Question 76

Fibonacci Heap insert

Answer 76

O(1)

Question 77

Fibonacci Heap deleteMin

Answer 77

O(n)

Question 78

Fibonacci Heap findMin

Answer 78

O(1)

Question 79

Fibonacci Heap decreaseKey

Answer 79

O(lgn)

Question 80

Fibonacci Heap delete

Answer 80

O(n)

Question 81

AVL tree find

Answer 81

0(lgn)

Question 82

AVL tree findMin

Answer 82

O(lgn)

Question 83

AVL tree findMax

Answer 83

O(lgn)

Question 84

AVL tree delete

Answer 84

O(lgn)

Question 85

AVL tree deleteMin

Answer 85

O(lgn)

Question 86

AVL tree deleteMax

Answer 86

O(lgn)

Question 87

AVL tree insert

Answer 87

O(lgn)