Week 7

Question 1

Max Heap

Answer 1

Binary tree data structure in which the value of any node is always greater than that of its children (heap property)
Largest value is the root of the tree
COMPLETE binary tree. Each level is filled before the next. filling from left to right.
Add/Remove : log n
Find largest: O(1)

Question 2

Heap underlying implementation

Formulat to find children/parent

Answer 2

Heap with max height h will have an array size of 2^h -1
Root of three at index 0
Node at index k:
- left child: index 2k +1
-right child: index 2k+2;
- parent at index (k-1)/2

Question 3

Adding value to heap, process

Answer 3

Place in the rightmost available spot of the deepest level of tree -> Bubble up

Question 4

Removing value from heap

Answer 4

Place right most element at deepest level at root position (can only remove elements from root) -> bubble down
When bubbling down it always switches with the larger to the two children nodes

Question 5

Is Heap a BST

Answer 5

NO, it is a BT but not a BST
Futhermore, children of a given node must be smaller than node but not necessary that smaller one is left and the other right

Question 6

How do we know we are done with bubbling down

Answer 6

Heap has not null leaves. Hence we know we are one if the indices of the left and right child of a given node are outside max capacity of array

Question 7

What is a Priority Queue

Answer 7

Java imlementation of Heap. But Min Heap and not Max Heap.

Question 8

Why do we require that heap uses a complete BT

Answer 8

Increase efficiency, as we have a interest to minimize height of BT

Question 9

What can be used in Priority Queue

Answer 9

Any Java object can be used as key as long as there exists means to compare any two instances in a way that defines a natural order of the keys

Question 10

Trie - Main appplication

Answer 10

Information retrieval
Tree like data structure that is efficient at storing strings in order to support fast pattern matching, in which each node holds a single character, an the nodes that are children of a node represent characters that follow that character in string

Question 11

Why Trie?

Answer 11

Storing strings in BST inefficient, every node start character by character comparison from beginning of string. would only need to check last added character

Question 12

Is Trie a Binary Tree

Answer 12

No

Question 13

Trie Definition

Answer 13

Tree-based data structure for storing strings in order to support fast pattern matching.

Question 14

Trie Properties - Structure

Answer 14

1. Each node, except the root is labeled with a character
2. The children of an non-leaf node have distinct labels
3. Each leaf is associated with a string. Concatenate characters along path
4. Height = length of longest string
5. # leaves = # strings stored
6. total number of nodes at most = n+1, n = total length of all strings
7. Use sentinel, e.g. null to mark end of string

Question 15

Trie - Time complexity

Answer 15

o(m), whre m is the length of the string, assuming a nodes stores its child nodes in an o(1) data strucutre.
if children stored e.g. in LL. need to traverse all X children of that node. complexity X*m

Question 16

Trie delete value

Answer 16

1. find word
2. remove sentinel,
3. move next node, if no children delte and move on
   else keep it and stop.