Huffman Coding

Huffman Coding (Greedy Approach)
Huffman coding is a lossless data compression algorithm that assigns variable-length codes to
input characters based on their frequencies. The greedy approach builds a binary tree by
repeatedly merging the least frequent characters into a single tree node.
Algorithm:
1. Build a priority queue (min-heap) where each node represents a character and its
frequency.
2. Extract two nodes with the lowest frequencies and create a new internal node with the
combined frequency.
3. Insert the new node back into the heap and repeat until only one node remains.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
// A node in the Huffman tree

struct MinHeapNode {
char data; // Character
unsigned freq; // Frequency of the character
struct MinHeapNode *left, *right; // Left and right child
};
// A Min Heap: a structure to build the Huffman tree

struct MinHeap {
unsigned size;
unsigned capacity;
struct MinHeapNode **array;
};
// Function to create a new min heap node

struct MinHeapNode* newNode(char data, unsigned freq) {
struct MinHeapNode* node = (struct MinHeapNode*) malloc(sizeof(struct
MinHeapNode));
node->left = node->right = NULL;
node->data = data;
node->freq = freq;
return node;
}
// Function to create a min heap

struct MinHeap* createMinHeap(unsigned capacity) {
struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct
MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**) malloc(minHeap->capacity *
sizeof(struct MinHeapNode*));
return minHeap;
}
// A utility function to swap two min heap nodes

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// To heapify a subtree with the root at index i

void minHeapify(struct MinHeap* minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->freq < minHeap-

>array[smallest]->freq)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->freq < minHeap-

>array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// Check if the size of the heap is one

int isSizeOne(struct MinHeap* minHeap) {
return (minHeap->size == 1);
}
// Extract the minimum value node from the heap

struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// Insert a new node into the Min Heap

void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
// Build the Huffman Tree

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i) {
minHeap->array[i] = newNode(data[i], freq[i]);
}
minHeap->size = size;
while (!isSizeOne(minHeap)) {
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);

top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
int main() {
char data[] = {'a', 'b', 'c', 'd', 'e'};
int freq[] = {5, 9, 12, 13, 16};
int size = sizeof(data) / sizeof(data[0]);
struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
// You can implement a function to print the Huffman codes here

// For now, we'll just print the final root of the Huffman Tree.
printf("Huffman Tree root frequency: %u\n", root->freq);
return 0;
}
Explanation:
 We use a min-heap to build the Huffman Tree.

 The greedy approach ensures that the least frequent nodes are combined first, leading to
an optimal prefix-free binary code.
4. Fractional Knapsack Problem
The fractional knapsack problem is a variation where you can take fractional parts of items. The
greedy approach selects items based on their value-to-weight ratio, starting with the highest ratio.
Algorithm:
1. Compute the value-to-weight ratio for each item.

2. Sort the items by this ratio in descending order.
3. Pick items from the sorted list, starting with the one having the highest ratio.
C Code:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int weight;
int value;
float ratio;
} Item;
// Comparator function to sort items by value-to-weight ratio

int compare(const void *a, const void *b) {
Item *itemA = (Item*)a;
Item *itemB = (Item*)b;
return (itemB->ratio - itemA->ratio) > 0 ? 1 : -1;
}
float fractionalKnapsack(Item items[], int n, int capacity) {

// Sort items by value-to-weight ratio in descending order
for (int i = 0; i < n; i++) {
items[i].ratio = (float)items[i].value / items[i].weight;
}
qsort(items, n, sizeof(Item), compare);
int remainingCapacity = capacity;

float maxValue = 0.0;
for (int i = 0; i < n; i++) {

if (items[i].weight <= remainingCapacity) {
remainingCapacity -= items[i].weight;
maxValue += items[i].value;
} else {
maxValue += items[i].value * ((float)remainingCapacity /
items[i].weight);
break;
}
}
return maxValue;
}
int main() {
Item items[] = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}};
int n = sizeof(items) / sizeof(items[0]);
int capacity = 50;
float result = fractionalKnapsack(items, n, capacity);

printf("Maximum value in Knapsack = %.2f\n", result);
return 0;
}

Huffman Coding

Uploaded by

Copyright:

Available Formats

Huffman Coding

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Huffman Coding

Uploaded by

Copyright:

Available Formats

Huffman Coding (Greedy Approach)

#define MAX_TREE_HT 100

// A node in the Huffman tree

// A Min Heap: a structure to build the Huffman tree

// Function to create a new min heap node

// Function to create a min heap

// A utility function to swap two min heap nodes

// To heapify a subtree with the root at index i

if (left < minHeap->size && minHeap->array[left]->freq < minHeap-

if (right < minHeap->size && minHeap->array[right]->freq < minHeap-

// Check if the size of the heap is one

// Extract the minimum value node from the heap

// Insert a new node into the Min Heap

// Build the Huffman Tree

top = newNode('$', left->freq + right->freq);

struct MinHeapNode* root = buildHuffmanTree(data, freq, size);

// You can implement a function to print the Huffman codes here

 We use a min-heap to build the Huffman Tree.

4. Fractional Knapsack Problem

1. Compute the value-to-weight ratio for each item.

// Comparator function to sort items by value-to-weight ratio

float fractionalKnapsack(Item items[], int n, int capacity) {

int remainingCapacity = capacity;

for (int i = 0; i < n; i++) {

float result = fractionalKnapsack(items, n, capacity);

You might also like