CMSC 401 Exam 2

Heap

A complete binary tree that:

• Max: every parent node is greater than or equal to its children

• Min: every parent node is less than or equal to its children
  Heaps are commonly used to implement priority queues.

Binary Search Tree

A binary tree data structure where for every node:

• All values in the left subtree are smaller than the node

• All values in the right subtree are larger than the node
  This property allows efficient searching, insertion, and deletion (typically O(log n) when balanced).

What is the main difference between a Binary Search Tree (BST) and a Heap?

The first maintains a global ordering property (left subtree < node < right subtree), which allows efficient searching for any element.

The second only maintains a parent-child ordering property (max or min at the root), which allows fast access to the largest or smallest element but does not support efficient searching for arbitrary elements.

Depth-First Search

A graph or tree traversal algorithm that explores as far down a branch as possible before backtracking. It typically uses a stack or recursion.

Breadth-First Search

A graph or tree traversal algorithm that explores nodes level by level, visiting all neighbors of a node before moving to the next level.
It typically uses a queue data structure.

How does Dijkstra’s Algorithm work?

1. Assigning distance 0 to the starting node and ∞ to all other nodes.

2. Repeatedly selecting the unvisited node with the smallest distance.

3. Updating the distances to its neighbors if a shorter path is found.

4. Marking the node as visited and repeating until all nodes are processed. graph algorithm used to find the shortest path from a starting node to all other nodes in a weighted graph, as long as all edge weights are non-negative.

using a priority queue (min-heap) to efficiently select the node with the smallest current distance.

Dijkstra’s Shortest Path Algorithm

A graph algorithm used to find the shortest path from a starting node to all other nodes in a weighted graph, as long as all edge weights are non-negative.