DSA PREFI AND FINALS

A heap is a specialized tree-based data structure that satisfies the heap property.

Property:

• Complete Binary Tree

• Efficient Storage

• Ordering Property

Heap Types

Max-Heap

-Parent node is always greater than or equal to its children

Min-Heap

-Parent node is always less than or equal to its children

Binary Heaps and Core Operations

• Insert (Enqueue)

        -Add element at end, then "bubble up" by swapping with parent until heap property         restored. Time: O(log n).

• Delete (Extract Root)

        -Remove root, move last element to root, then "bubble down" by swapping with         smaller/larger child. Time: O(log n).

• Heapify

        -Convert arbitrary array into heap structure. Time: O(n) using bottomup approach with sift-        down operations.

Heap Applications and Real-World Impact

Heap Sort

-O(n log n) sorting algorithm; builds heap, repeatedly extracts maximum element

Priority Queues

-Operating systems use heaps for process scheduling and task prioritization

Dijkstra's Algorithm

-Min-heaps accelerate shortest path finding in weighted graphs

Median Finder

-Two heaps maintain running median in data streams efficiently

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (links). Graphs model relationships and networks, making them essential for representing social connections, transportation systems, web pages, and molecular structures.

Vertices

Individual nodes in the network representing entities or points

Edges

Connections between vertices representing relationships or paths

Two fundamental properties classify graphs: directed (edges have direction) versus undirected (symmetric relationships), and weighted (edges have values) versus unweighted (uniform edge importance).

Directed - one-way

Undirected - bidirectional

Adjacency Matrix

-2D array where entry [i][j] indicates connection between vertices i and j. Dense representation; O(1) edge lookup. Space: O(V²).

Adjacency List

-Array of linked lists or hash maps storing neighbors for each vertex. Sparse representation; efficient for sparse graphs. Space: O(V+E).

Breadth-First Search (BFS)

-Explores vertices in layers from source. Uses queue data structure.

Depth-First Search (DFS)

-Explores as far as possible along each branch before backtracking. Uses stack or recursion.

A hash table is a data structure that stores data in key-value pairs. It uses a hash function to compute an index (called a hash code) into an array of buckets or slots, from which the desired value can be found quickly.

Structure of a Hash Table

1. Array (Buckets): A fixed-size array where each slot can hold one or more elements.

2. Hash Function: A mathematical function that maps a key to an index in the array.

3. Keys and Values: Each stored item has a key and its corresponding value.

• The key is a unique identifier for the data.

• The value is the data associated with that key.

A collision occurs when two or more keys hash to the same index.

The two main techniques are:

1. Chaining

• Each index in the hash table stores a linked list (or another dynamic structure) of all elements that hash to the same index.

• When a collision happens, the new element is simply added to the list at that index.

2. Open Addressing

• All elements are stored within the array itself.

• When a collision occurs, the hash table searches for another empty slot based on a specific probing strategy.

Common Probing Methods

1. Linear Probing: Check the next index until an empty slot is found. (index + 1, index + 2, etc.)

2. Quadratic Probing: Check slots using a quadratic function. (index + 1², index + 2², etc.)

3. Double Hashing: Use a second hash function to determine the step size for probing.

A binary tree is a hierarchical data structure in which each node has at most two children, known as the left child and right child.

Tree Traversal Techniques

In-order - Left → Root → Right

Pre-order - Root → Left → Right

Post-order - Left → Right → Root

A balanced tree is a type of binary tree where the height difference between the left and right subtrees of any node is kept small — usually no more than one level apart.

Types of Balanced Trees

1. AVL Tree (Adelson-Velsky and Landis Tree)

• The height difference (balance factor) between left and right subtrees of any node is at most 1.

2. Red-Black Tree

A self-balancing binary search tree that uses color properties (red or black) on nodes to keep the tree approximately balanced.

Bubble Sort

-Repeatedly scan the list and swap adjacent out-of-order items until no swaps remain.

Selection Sort

-Repeatedly find the minimum element from the unsorted portion and swap it into place.

Insertion Sort

-Build a sorted prefix by inserting each new element into its correct position by shifting larger elements right.

Merge Sort

-Split list into halves recursively, sort each half, then merge two sorted halves into one sorted output.

Quick Sort

-Choose a pivot, partition elements into less/greater groups, then recursively sort partitions.

Linear Search

Scan each element until the target is found or list ends.

Binary Search

Requires sorted array. Compare target to middle, then search left or right half repeatedly.