DS – codingwithskills.com

				
					#include <stdio.h>
#include <stdlib.h>

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify to maintain heap property
void heapify(int *heap, int size, int i, int is_min_heap) {
    int extreme = i, left = 2 * i + 1, right = 2 * i + 2;

    if (is_min_heap) { // Min Heap
        if (left < size && heap[left] < heap[extreme]) extreme = left;
        if (right < size && heap[right] < heap[extreme]) extreme = right;
    } else { // Max Heap
        if (left < size && heap[left] > heap[extreme]) extreme = left;
        if (right < size && heap[right] > heap[extreme]) extreme = right;
    }

    if (extreme != i) {
        swap(&heap[i], &heap[extreme]);
        heapify(heap, size, extreme, is_min_heap);
    }
}

// Build a heap from an array
void buildHeap(int *heap, int size, int is_min_heap) {
    for (int i = (size - 2) / 2; i >= 0; i--)
        heapify(heap, size, i, is_min_heap);
}

// Delete an element from the heap
void deleteElement(int *heap, int *size, int key, int is_min_heap) {
    int i;
    for (i = 0; i < *size; i++) {
        if (heap[i] == key) break;
    }

    if (i == *size) {
        printf("Element %d not found.\n", key);
        return;
    }

    heap[i] = heap[--(*size)];
    heapify(heap, *size, i, is_min_heap);
}

// Display the heap
void displayHeap(int *heap, int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", heap[i]);
    printf("\n");
}

int main() {
    int minHeap[] = {3, 2, 1, 7, 8, 4, 10, 16};
    int maxHeap[] = {10, 8, 16, 14, 7, 9, 3, 2};
    int minSize = sizeof(minHeap) / sizeof(minHeap[0]);
    int maxSize = sizeof(maxHeap) / sizeof(maxHeap[0]);

    // Build and display Min Heap
    buildHeap(minHeap, minSize, 1);
    printf("Min Heap:\n");
    displayHeap(minHeap, minSize);

    // Build and display Max Heap
    buildHeap(maxHeap, maxSize, 0);
    printf("Max Heap:\n");
    displayHeap(maxHeap, maxSize);

    // Delete elements and display heaps
    deleteElement(minHeap, &minSize, 4, 1);
    printf("Min Heap after deleting 4:\n");
    displayHeap(minHeap, minSize);

    deleteElement(maxHeap, &maxSize, 16, 0);
    printf("Max Heap after deleting 16:\n");
    displayHeap(maxHeap, maxSize);

    return 0;
}







Output:-
Min Heap:
1 2 3 7 8 4 10 16
Max Heap:
16 14 10 8 7 9 3 2
Min Heap after deleting 4:
1 2 3 7 8 16 10
Max Heap after deleting 16:
14 8 10 2 7 9 3

				
					#include <stdio.h>

// Utility function to get maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to solve the 0/1 Knapsack problem
void knapsack(int weights[], int values[], int n, int capacity) {
    int dp[n + 1][capacity + 1];

    // Build the dp table
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0; // Base case
            } else if (weights[i - 1] <= w) {
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // Output the maximum value
    printf("Maximum value in Knapsack = %d\n", dp[n][capacity]);

    // Traceback to find included items
    printf("Items included:\n");
    int w = capacity;
    for (int i = n; i > 0 && dp[i][w] > 0; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            printf("Item %d (Weight: %d, Value: %d)\n", i, weights[i - 1], values[i - 1]);
            w -= weights[i - 1];
        }
    }
}

int main() {
    int n, capacity;

    // Input number of items and their weights and values
    printf("Enter the number of items: ");
    scanf("%d", &n);

    int weights[n], values[n];
    printf("Enter the weights of the items:\n");
    for (int i = 0; i < n; i++) scanf("%d", &weights[i]);
    printf("Enter the values of the items:\n");
    for (int i = 0; i < n; i++) scanf("%d", &values[i]);

    // Input knapsack capacity
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);

    // Solve the knapsack problem
    knapsack(weights, values, n, capacity);

    return 0;
}

















/*input*/

Enter the number of items: 3
Enter the weights of the items:
10 20 30
Enter the values of the items:
60 100 120
Enter the capacity of the knapsack: 50


//output

Maximum value in Knapsack = 220
Items included:
Item 3 (Weight: 30, Value: 120)
Item 2 (Weight: 20, Value: 100)

Theory on Min Heap Construction, Deletion, and Display

Min Heap Overview

A Min Heap is a binary tree data structure where:

The value of each parent node is smaller than or equal to its children.
The tree is complete, meaning all levels except possibly the last are fully filled, and the last level is filled from left to right.

Min Heaps are typically implemented using arrays for efficiency. The key advantage is that we can find the smallest element (root) in constant time $O (1)$ , making Min Heaps useful for priority queues.

Representation in Arrays

Indexing:
- The root element is at index 0.
- For an element at index $i$ :
  - Left child: $2 i + 1$
  - Right child: $2 i + 2$
  - Parent: $⌊(i−1)/2⌋\lfloor (i-1)/2 \rfloor$
Operations in Min Heap:
- Insert: Add the element at the end of the array and “heapify up” to restore the heap property.
- Delete: Replace the element to be deleted with the last element, remove the last element, and “heapify down” to restore the heap property.
- Heapify: A process of rearranging elements to satisfy the heap property.
  - Heapify Up: Moves an element upward by comparing it with its parent.
  - Heapify Down: Moves an element downward by comparing it with its children.

Steps to Construct a Min Heap

Insert elements one by one into an initially empty heap.
After inserting each element, use the “heapify up” method to maintain the heap property.

Alternatively, if the input array is known in advance:

Use a heapify algorithm to construct the heap in $O (n)$ time.

Steps to Delete an Element

Identify the index of the element to be deleted.
Replace the element with the last element in the heap.
Remove the last element.
Use “heapify down” to restore the heap property.

Example Heap Array Operations

Consider the array:
$3, 1, 6, 5, 2, 8, 7$

Construct Min Heap:
After constructing, the heap may look like:
$1, 2, 6, 5, 3, 8, 7$
Delete Element (e.g., 6):
- Replace $6$ with $7$ (last element).
- Remove the last element.
- Heapify down to get:
  $1, 2, 7, 5, 3, 8$
Display the Heap Content:
The heap array remains ready for display or further operations.

Advantages of Min Heap

Efficient extraction of the minimum element ( $O (1)$ ).
Insertion and deletion are efficient ( $O(log⁡n)O(\log n)$ ).
Useful for sorting (Heap Sort) and implementing priority queues.

2.>

Comparing Performance of Single Source Shortest Paths (Greedy Method) with Adjacency Matrix vs. Adjacency List

The Single Source Shortest Path (SSSP) problem aims to find the shortest paths from a source vertex to all other vertices in a graph. A popular algorithm to solve this problem is Dijkstra’s Algorithm, which employs the greedy method. The performance of Dijkstra’s Algorithm depends significantly on the graph’s representation—Adjacency Matrix or Adjacency List.

1. Adjacency Matrix Representation

Structure:
The graph is represented as a $\times V$ matrix, where $V$ is the number of vertices.
- $ma t r i x [u] [v]$ contains the weight of the edge from vertex $u$ to vertex $v$ .
- If there is no edge between $u$ and $v$ , $ma t r i x [u] [v]$ is $∞\infty$ (or 0 for unweighted graphs).
Advantages:
- Checking for the existence of an edge between two vertices is $O (1)$ .
- Useful for dense graphs, where most vertices are connected.
Disadvantages:
- Space complexity is $O(V^2)$ , which can be inefficient for sparse graphs.
- Iterating over all neighbors of a vertex requires $O (V)$ , even if the vertex has only a few edges.

2. Adjacency List Representation

Structure:
The graph is represented as an array of lists. Each list contains the neighbors of a vertex and their corresponding edge weights.
- $l i s t [u]$ contains pairs $(v, w)$ , where $v$ is a neighbor of $u$ and $w$ is the weight of the edge $(u, v)$ .
Advantages:
- Space complexity is $O (V + E)$ , which is efficient for sparse graphs ( $\ll V^2$ ).
- Iterating over all neighbors of a vertex takes $u)O(\text{degree of } u)$ , which is faster for sparse graphs.
Disadvantages:
- Checking for the existence of a specific edge is slower ( $u)O(\text{degree of } u)$ ) compared to $O (1)$ in adjacency matrix.

3. Performance Comparison

Aspect	Adjacency Matrix	Adjacency List
Space Complexity	$O(V^2)$	$O (V + E)$
Initialization	$O(V^2)$	$O (V + E)$
Extract Min (Greedy)	$O (V)$ with array, $O(log⁡V)O(\log V)$ with heap	$O (V)$ with array, $O(log⁡V)O(\log V)$ with heap
Relaxation of Edges	$O (V)$	$u)O(\text{degree of } u)$
Overall Time Complexity	$O(V^2)$ with simple array; $O(V^2)$ with binary heap	$V\log V)$ with binary heap

Key Insights

Adjacency Matrix:
- Best for dense graphs where $\approx V^2$ .
- Simpler implementation but less efficient for sparse graphs.
Adjacency List:
- Best for sparse graphs where $\ll V^2$ .
- More space-efficient and faster edge relaxation due to fewer edges per vertex.
Heap Usage:
- Using a binary heap for the priority queue in Dijkstra’s Algorithm improves performance.
- With adjacency list, time complexity becomes $V\log V)$ , which is optimal for sparse graphs.

Conclusion

For dense graphs, an adjacency matrix is viable but can become inefficient due to higher space and time requirements.
For sparse graphs, adjacency lists paired with a priority queue (like a binary heap) offer better performance due to lower space usage and faster edge relaxation.
Understanding the graph structure and choosing the right representation significantly impacts the algorithm’s performance.