EXAM 3 FOCUS (Heaps, Hash Tables, Graphs, BST)

Heap property (min-heap)

Parent node is always smaller than its children

Heap stored how

Using an array representing a complete binary tree

Heap insert complexity

O(log n)

Heap remove-min complexity

O(log n)

Heap find-min complexity

O(1)

Percolate up purpose

Restore heap order after insert

Percolate down purpose

Restore heap order after deletion

Index of left child in heap

2*i + 1

Index of right child in heap

2*i + 2

Index of parent in heap

(i - 1) / 2

Why heap is not a BST

Heap only ensures heap-order, not sorted in subtrees

Hashing definition

Mapping keys to indices using a hash function

Collision definition

Two keys map to the same index

Collision handling methods

Chaining or open addressing

Load factor formula

Number of elements / table size

Hash table average search time

O(1)

Hash table worst-case search time

O(n)

Chaining advantage

Simple, flexible collision resolution

Linear probing issue

Primary clustering

Quadratic probing purpose

Reduces clustering

Double hashing purpose

Avoids clustering by changing step size

Graph adjacency list

Each vertex stores a list of neighbors

Graph adjacency matrix

VxV matrix storing edge values

BFS uses what

Queue

DFS uses what

Stack or recursion

BFS complexity

O(V + E)

DFS complexity

O(V + E)

Directed graph definition

Edges have direction

Undirected graph definition

Edges have no direction

Tree vs graph

Tree is acyclic, graph may contain cycles

BST property

Left child < root < right child

BST search average

O(log n)

BST search worst-case

O(n)

BST insert complexity

O(log n) average, O(n) worst

Inorder traversal produces

Sorted order

Min value in BST

Leftmost node

BST delete worst-case

O(n)

BST height relation

Affects all BST operations