Data structures

Question 1

Implementation of Breadth First Search uses what?

Answer 1

Queue - add child nodes . shift off node from front.

repeat until queue is empty

Question 2

Implementation of Depth First Search uses?

Answer 2

Stack - add nodes. remove end nodes from end.

Often recursion.

Question 3

what is a heap? (2 types)

Answer 3

binary tree where children are smaller (max heap) or larger (min heap) than parent. Root node is smallest (min heap) or largest (max heap)

Question 4

what is heapifying?

Answer 4

looping through heap and swapping up/down nodes depending on min/max

Question 5

insert into heap?

Answer 5

add as leaf node, then heapify

Question 6

heap sort?

Answer 6

1 - build a heap from unsorted array
2 - take root node and swap with last element, then remove that last element to ‘sorted’ array
3 - re-heapify the heap
4 - repeat

Question 7

index of heap last parent node in an array

Answer 7

array.length (rounded down) - 1