Awesome q2a theme
0 votes
13 views
What is the time complexity of the following code?

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

typedef struct{
    char data;
    unsigned int freq;
    unsigned int parent, leftChild, rightChild;
}HTNode, *HuffmanTree;
typedef char** HuffmanCode;

void Select(HuffmanTree T, int n, int&l, int&r){
    HuffmanTree p = T+1; 
    int a = 0, b = 0;
    for(int i = 1; i <= n; i++, p++){
        if(!p->parent){
            if(!a){
                l = i; 
                a = 1;
            }
            else if(!b){
                r = i; 
                b = 1;
            }
            else if(p->freq < (T+l)->freq||p->freq < (T+r)->freq){
                if((T+l)->freq <= (T+r)->freq)r = i;
                else l = i;
            }
        }
    }
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, char* c, int n){
    if(n <= 1) return;
    int m = 2*n-1, i;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
    HuffmanTree p;
    for(p = HT+1, i = 1; i <= n; i++, p++, w++) 
        *p = {c[i-1], *w, 0, 0, 0};
    for(i = n+1; i <= m; i++, p++)
        *p = {0, 0, 0, 0, 0};
    for(i = n+1; i <= m; i++){
        int s1, s2;
        Select(HT, i-1, s1, s2);
        HT[s1].parent = i; 
        HT[s2].parent = i;
        HT[i].leftChild = s1; 
        HT[i].rightChild = s2;
        HT[i].freq = HT[s1].freq + HT[s2].freq;
    }
    HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
    char* cd = (char *)malloc(n*sizeof(char));
    cd[n-1] = '\0';
    for(i = 1; i <= n; i++){
        int start = n-1, c, f;
        for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
            if(HT[f].leftChild == c) cd[--start] = '0';
            else cd[--start] = '1';
        HC[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy(HC[i], &cd[start]);
    }
    free(cd);
}

void PrintHuffmanCode(HuffmanCode HC, int* w, char* c, int n){
    for(int i = 1; i <= n; i++){
        printf("Character: %c, ", c[i-1]);
        printf("bits: %d, ", strlen(HC[i]));
        printf("frequency: %d, ", w[i-1]);
        printf("code: %s, ", HC[i]);
        printf("total bits: %d\n", strlen(HC[i])*w[i-1]);
    }
}

char* EnCode(HuffmanCode HC, char* c, char ch, int n){
    for(int i = 0; i < n; i++){
        if(c[i] == ch){
            char *p = HC[i+1];
            return p;
        }
    }
}

int main(){
    int i = 0, w[1000] = {0}, *word, j = 0; 
    char *c, s[] = {"ABCD"};
    while(s[i] != '\0'){
        w[s[i]+500]++;
        i++;
    }
    word = (int*)malloc(sizeof(int));
    c = (char*)malloc(sizeof(char));
    for(i = -500; i < 500; i++){
        if(w[i+500] != 0){
            word = (int*)realloc(word,(j+1)*sizeof(int));
            c = (char*)realloc(c,(j+1)*sizeof(char));
            word[j] = w[i+500];
            c[j] = i;
            j++;
        }
    }
    const int len = j; 
    HuffmanCode HC;
    HuffmanTree HT;
    HuffmanCoding(HT, HC, word, c, len);
    PrintHuffmanCode(HC, word, c, len);
    return 0;
}

in Algorithms by (5 points) | 13 views
0
Not going to read all that, but huffman coding is O(nlogn)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,092 questions
3,152 answers
14,579 comments
95,935 users