Heap and Heap Sort; Graph — Introduction; Graph Representations

Heap and Heap Sort

What is a Heap?

A Heap is a complete binary tree satisfying the heap property:

• Max-Heap: Every parent ≥ its children (root = maximum element)
• Min-Heap: Every parent ≤ its children (root = minimum element)

Max-Heap:
           [90]
          /    \
       [70]    [80]
       /  \   /  \
     [50][60][75][30]

Heap Implementation using Array

// Heap stored in array: parent at i, children at 2i+1 and 2i+2
int heap[100];
int n = 0;  // heap size

int parent(int i) { return (i - 1) / 2; }
int left_child(int i) { return 2 * i + 1; }
int
right_child(int i) { return 2 * i + 2; }

// Insert into max-heap
void heap_push(int value) {
    heap[n++] = value;
    int i = n - 1;
    // Bubble up
    while (i > 0 && heap[parent(i)] < heap[i]) {
        // swap
        int temp = heap[parent(i)];
        heap[parent(i)] = heap[i];
        heap[i] = temp;
        i = parent(i);
    }
}

Heap Sort Algorithm

1. Build a Max-Heap from the input array (heapify)
2. Repeat:
   a. Swap root (max) with last element
   b. Reduce heap size by 1
   c. Heapify root to restore heap property
3. Array is now sorted in ascending order

Complexity: O(n log n) — guaranteed; in-place.

Graph — Introduction

What is a Graph?

A Graph is a collection of vertices (nodes) and edges (connections) between them.

G = (V, E)
V = set of vertices
E = set of edges

Real-world examples:

• Social networks (friends = vertices, connections = edges)
• Road networks (cities = vertices, roads = edges)
• Computer networks (computers = vertices, links = edges)
• Internet web pages (pages = vertices, links = edges)

Types of Graphs

Graph Terminology

Graph Representations

16.1 Adjacency Matrix

A 2D array where matrix[i][j] = 1 if edge exists between vertex i and j.

Graph:    0---1---2
          |       |
          3-------+

Matrix:    0  1  2  3
        0 [0, 1, 0, 1]
        1 [1, 0, 1, 0]
        2 [0, 1, 0, 1]
        3 [1, 0, 1, 0]

Adjacency Matrix in C:

int adj[5][5] = {0};  // initialize to 0

void add_edge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1;  // for undirected graph
}

Pros: O(1) to check if edge exists Cons: O(V²) space even for sparse graphs

16.2 Adjacency List

Array of linked lists. Each index i contains a list of vertices adjacent to i.

0: [1] → [3] → NULL
1: [0] → [2] → NULL
2: [1] → [3] → NULL
3: [0] → [2] → NULL

Adjacency List in C:

typedef struct node {
    int vertex;
    struct node *next;
} node_t;

node_t *adj[MAX_V];  // array of linked lists

void add_edge(int u, int v) {
    // Add v to u's list
    node_t *new_v = malloc(sizeof(node_t));
    new_v->vertex = v;
    new_v->next = adj[u];
    adj[u] = new_v;

    // Add u to v's list (undirected)
    node_t *new_u = malloc(sizeof(node_t));
    new_u->vertex = u;
    new_u->next = adj[v];
    adj[v] = new_u;
}

Pros: O(V + E) space; efficient for sparse graphs Cons: O(degree) to check if specific edge exists

Matrix vs List Comparison