Hansung

Question 1

What is a heap?

Answer 1

A binary tree with two constraints
- It is complete
- Each child has a value “greater than or equal to” it sparent

Question 2

How do you add to a heap?

Answer 2

• add the element to the next available space in the tree
• Percolate the value up the tree to maintain the correct ordering

Question 3

What data structures use heaps?

Answer 3

Priority Queues

Question 4

How does removeMin work on priority queues?

Answer 4

• Pop the root
• Replace it with the last element in the heap
• Percolate this element down to the bottom of the heap choosing the minimum child

Question 5

How do we navigate a heap?

Answer 5

• The root of the tree is at array location 0
• The last element is size()-1
• The parent of a node k is at floor((k-1)/2)
• The children of node k are at array locations 2k + 1 and 2k + 2

Question 6

What is the time complexity of perlocating in a heap?

Answer 6

Ɵ(1)

Question 7

What is the time complexity of the height of the tree?

Answer 7

Ɵ(log(n))

Question 8

What is the time complexity of add/removeMin on a heap?

Answer 8

Ɵ(log(n)) in worst case
Ɵ(1) normally

Question 9

What is the worst case time complexity of Heap sort?

Answer 9

O(n log(n))

Question 10

What is the space complexity of heap sort?

Answer 10

O(1)

Question 11

What is a B-tree?

Answer 11

Balanced multiway trees made for fast search, finding successors/predecessors, insert, delete, maximum, minimum

Question 12

What are M-way trees?

Answer 12

Trees where each non-leaf node has M children

Question 13

What is the access time of a M-way tree?

Answer 13

Logm(n) = Log2(n)/Log2(m)

Question 13

What makes B+ trees different to B-Trees

Answer 13

• Only leaf nodes contain data pointers, while internal nodes contain keys only
• Sequential access is possible like a linked list
• Searching is faster
• Insertion and Deletion are easier and faster

Question 13

What makes B-Trees different to B+ Trees?

Answer 13

• All internal nodes and leaf nodes contain data pointers along with keys
• Sequential access of nodes is not possible
• Searching is slower
• Insertion and Deletion take more time

Question 14

What values should you use for M in B+ trees?

Answer 14

Odd numbers

Question 15

What is a Trie?

Answer 15

A multiway tree often used for storing large sets of words

Question 16

How do tries work?

Answer 16

• They are trees with a possible branch for every letter of an alphabet
• All words end with a special letter “$”
• They compactify the edges in the tree in order to remove: internal and external one-way branching

Question 17

What are the uses of Tries?

Answer 17

• Way of implementing sets
• Provide quick insertion, deletion and find
• Good for spell checkers, completion, algorithm

Question 18

What are the disadvantages of Tries?

Answer 18

• Waste large amounts of memory

Question 19

How are Binary Tries different from Normal Tries?

Answer 19

They speeds up finds but loses the advantage of multiway trees by reducing the depth

Question 20

Why use Tries?

Answer 20

• Classic memory, time complexity trade-off
• Specialist
• Not too complicated to implement