CODEWITHSUNDEEP
carraysalgorithm
user3206225
user3206225

Reputation: 161

huffman implementation without sorting

I want to implement huffman without sorting. the idea is i add first two elements and add the result obtained at the last of the the array.eg.

(1) data[256]= {1 2 3 4 5}. we add first two elements and we get "3" which we put at last of the array like this {1 2 3 4 5 3}. this was the first execution. my logic data[data_size].freq=data[f].freq+data[s].freq; data_size++; do it well.

(2) Now in the second execution i want to add the result obtained by the previous addition (which is at locataion data_size) and the next element of the array. so the logic to do it must be like this: data[data_size].freq=data[data_size].freq+data[s].freq; Now the result will be {1 2 3 4 5 3 **6**} .I don't have to sort, this has to be implemented withou any sorting . the added elements must stay at the last position of array. But the addition must always be between the element at data[data_size].freq (this is obtained by addition of first two elements in first execution and after first executuion it must be the result of addition of last element obtained by addition of first of two elements and element at odd poition, i mean "s") and data[s].freq (it is element at "s" position).

I have the idea to do but the problem is if i add at first two position (for the very first execution where i get the first element obtained at the last of array index by addtion of elements at index 0 and 1) like :

newItem.freq = data[i].freq + data[j].freq; data[dataSize++]=newItem;

Now i have to do: 

 newItem.freq = data[dataSize].freq + data[j].freq;
here i have problem in writting it's code.

Upvotes: 0

Views: 84

Answers (1)

anumi
anumi

Reputation: 3947

You should use a priority queue.All the elements are first places in the priority queue. Then, at each step two smallest elements are taken, combined, and the result is pushed back to the queue.

Upvotes: 1

Related Questions