霍夫曼执行不排序 [英] huffman implementation without sorting

问题描述

我想实现霍夫曼不排序。 这个想法是我加上前两个元素，并添加在最后的array.eg所获得的结果。

（1）数据[256] = {1 2 3 4 5}。我们先添加两个元素，我们可以得到3，我们把最后是这样的阵列{1 2 3 4 5 3 }。这是第一次执行。我的逻辑 数据[DATA_SIZE] .freq =数据[F] .freq +数据[S] .freq; DATA_SIZE ++; 做得很好

。

（2）现在，在第二执行我想添加由previous加成（于locataion DATA_SIZE）获得的结果和所述阵列的下一个元素。这样的逻辑来做到这一点，必须是这样的：数据[DATA_SIZE] .freq =数据[DATA_SIZE] .freq +数据[S] .freq; 现在的结果是 {1 2 3 4 5 3 ** ** 6} 我没有进行排序，这已经被withou任何实施分选。添加的元素必须留在阵中最后一个位置。但是，除了必须始终元素之间的数据[DATA_SIZE] .freq （这是由另外在第一次执行前两个要素获得与第一executuion后，它必须是此外，加入前两个元素和元素在奇数poition的获得最后一个元素的结果是，我的意思是S）和数据[S] .freq （这是元素在S的位置）。

我有这个想法做的，但问题是，如果我的前两个位置添加（对于第一个执行从哪里获得在最后通过的元素addtion数组索引中获得的第一个元素的索引0和1），如

newItem.freq =数据[I] .freq +数据[J] .freq;       数据[数据大小++] =的newitem;

现在我要做的：

  newItem.freq =数据[数据大小] .freq +数据[J] .freq;
在这里，我有书面方式是code问题。
 

解决方案

您应该使用优先queue.All的元素优先级队列中第一个地方。然后，在每一步两个最小元素被取，合并，并将结果推回队列

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.

解决方案

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.

这篇关于霍夫曼执行不排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！