Data Structures

What is a Heap (2 answers)

• A special tree-based data structure where the tree is a complete (or almost complete) binary tree.

• It is a minimum height binary tree where the deepest level is filled from left to right.

Min Heap

When a smaller value has a higher priority than a larger one

Max Heap

When a larger value has a higher priority than a smaller one

Does a heap order care about the relative order of the siblings

No, it is only concerned with the value of its descendants.

Time complexity for Heap insertion

O(log(n))

What is the best strength/utility of a Heap

That the smallest or largest value can be found in O(1) time.

Insert method steps (Heap)

1. Insert value into heap

2. Perform upheap

3. Increment next counter

Upheap Steps

1. Compare the inserted node with its parent.

2. If node is smaller than parent, swap, continue up.

3. If parent is smaller than node, stop.

Delete method steps (Heap)

1. If root has no children, delete.

2. Swap root with last leaf, delete.

3. Perform Downheap.

Downheap Steps

1. Compare parent, left, and right

2. If parent is smallest then stop

3. if left is smallest then swap with parent and continue left.

4. if right is smallest then swap with parent and continue right.

For a given node i in a heap, what are its left, right, and parent

• Its Left Child is at position 2 * i

• Its Right Child is at position 2 * i + 1

• Its Parent is at position int i/2 (aka the floor)

Graph Concept

A set of nodes (vertices) and a set of edges (arcs) used to model abstracted versions of real-life systems.

Common Graph use cases

• Relationship data

• Location data

• Network data

Graph Paths Concept

A path is an ordered collection of node-edge transitions.

Graph types

• Undirected

• Directed

• Cyclic

• Acyclic

• Weighted

• Unweighted

• Sparse

• Dense

Directed/Undirected Graphs

• A graphs edges can optionally have a direction (i.e. a directed graph).

• If there is a direction, movement must follow that direction.

• If an edge has no direction, movement can go both ways.

Weighted/Unweighted

• An edge can have a weight (cost) (i.e. a weighted graph).

• The transition from one node to another costs that weight.

• This could represent the distance, or time, or anything you want to represent.

• Edges without weights are unweighted

Cyclic/Acyclic

• Cycles begin at the same node and contain at least one edge.

• A graph without cycles is called Acyclic

Sparse/Dense

• Dense is where there are many edges(arcs) present.

• Sparse is when there are edges (arcs) missing.

Graph Traversal Methods (2 answers)

• Depth-First Traversal

• Breadth-First Traversal

Depth-First Traversal Utility

• Finding cycles

• Finding valid paths

• Identifying connected nodes

• Can travel very deep into the graph

Depth-First Traversal Algorithm

1. Randomly pick a starting node, mark it as visited

2. Recursively move to an adjacent node, keeping track of visited nodes.

3. Eventually you will arrive at a node that has no non-visited adjacent nodes.

4. When you do, backtrack to the previous node.

Breadth-First Traversal Utility

Travels a short distance but finds the shortest path on unweighted graphs

Dijkstra’s algorithm

Finds the shortest path on weighted graphs (no negatives)

Breadth-First Traversal Algorithm

1. Randomly pick a starting node, mark it as visited

2. Identify all adjacent nodes.

3. Recursively visit them, keeping track of visited nodes

4. Continue until all nodes have been visited

Adjacency Matrix

Good for dense graphs, 1 is for if there is an edge connecting the nodes and 0 is if there is no edge.

Adjacency List

1. Good for sparse graphs

2. List with all the nodes

3. Keeps track of its neighbours.