霍夫曼在C中编码，并保存顺序

Question

c以实现（a）近似订购订单的霍夫曼编码的算法 - 每个阶段合并两个相邻子树，其权重的总和最小。输入是1）正整数n和2）n个正整数的序列给出频率计数（权重）用于有序字符集中的符号。

仅当叶顺序为与字符集的顺序一致。

我必须修改以下代码以使以上代码成为可能：

    // Huffman code using a minHeap with handles (index-heap-based priority queue).
// Heap routines are adapted from "Algorithms in C, Third Edition", and
// "Algorithms in Java, Third Edition", Robert Sedgewick
// This is a prototype for demonstration purposes only.
// Minimally, the heap/priority queue implementation should
// be in a different source file.
#include <stdio.h>
#include <stdlib.h>
int N,          // Number of items in queue
        *pq,        // Priority queue
        *qp,        // Table of handles (for tracking)
        maxQueued;  // Capacity of priority queue
double *a;      // Pointer to user's table
void exch(int i, int j) {
// Swaps parent with child
    int t;
    t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
    qp[pq[i]] = i;
    qp[pq[j]] = j;
}
void PQinit(double *items, int n, int m) {
    int i;
    a = items;    // Save reference to index table
    maxQueued = m;
    N = 0;
    pq = (int*) malloc((maxQueued + 1) * sizeof(int)); // Contains subscripts to a[]
    qp = (int*) malloc(n * sizeof(int)); // Inverse of pq, allows changing priorities
    if (!pq || !qp) {
        printf("malloc failed %dn", __LINE__);
        exit(0);
    }
// Set all handles to unused
    for (i = 0; i < n; i++)
        qp[i] = (-1);
}
int PQempty() {
    return !N;
}
int PQfull() {
    return N == maxQueued;
}
int less(int i, int j) {
// Notice how heap entries reference a[]
    return a[pq[i]] < a[pq[j]];
}
void fixUp(int *pq, int k) // AKA swim
{
    while (k > 1 && less(k, k / 2)) {
        exch(k, k / 2);
        k = k / 2;
    }
}
void fixDown(int *pq, int k, int N) // AKA sink
{
    int j;
    while (2 * k <= N) {
        j = 2 * k;
        if (j < N && less(j + 1, j))
            j++;
        if (!less(j, k))
            break;
        exch(k, j);
        k = j;
    }
}
void PQinsert(int k) {
    qp[k] = ++N;
    pq[N] = k;
    fixUp(pq, N);
}
int PQdelmin() {
    exch(1, N);
    fixDown(pq, 1, --N);
    qp[pq[N + 1]] = (-1);  // Set to unused
    return pq[N + 1];
}
void PQchange(int k) {
    fixUp(pq, qp[k]);
    fixDown(pq, qp[k], N);
}
// main implements Huffman code.
// Index is just a table of priorities whose
// subscripts are used in the PQ.
main() {
    int n, m, op, i, j, val;
    double *priority, probSum, expected = 0.0;
    int *left, *right;  // Links for Huffman code tree, root is subscript m-1
    int *parent;  // For printing the codes
    int *length;
    char *outString;
    printf("Enter alphabet sizen");
    scanf("%d", &n);
    m = 2 * n - 1;  // Number of nodes in tree
    priority = (double*) malloc(m * sizeof(double));
    left = (int*) malloc(m * sizeof(int));
    right = (int*) malloc(m * sizeof(int));
    parent = (int*) malloc(m * sizeof(int));
    outString = (char*) malloc((n + 1) * sizeof(char));
    length = (int*) malloc(m * sizeof(int));
    if (!priority || !left || !right || !parent || !outString || !length) {
        printf("malloc problem %dn", __LINE__);
        exit(0);
    }
    PQinit(priority, m, n);
    for (i = 0; i < n; i++)
        priority[i] = (-1);
// Read and load alphabet symbols' probabilities into priority queue.
    probSum = 0.0;
    for (i = 0; i < n; i++) {
        scanf("%lf", priority + i);
        probSum += priority[i];
        PQinsert(i);
        left[i] = right[i] = (-1);
    }
    printf("Probabilities sum to %fn", probSum);
// Huffman code tree construction
    for (i = n; i < m; i++) {
        left[i] = PQdelmin();
        right[i] = PQdelmin();
        parent[left[i]] = parent[right[i]] = i;
        priority[i] = priority[left[i]] + priority[right[i]];
        PQinsert(i);
    }
    i = PQdelmin();
    if (i != m - 1) {
        printf("The root isn't the rootn");
        exit(0);
    }
    parent[m - 1] = (-1);
// Goes breadth-first from root to compute length of prefix bit codes.
    length[m - 1] = 0;
    for (i = m - 1; i >= n; i--)
        length[left[i]] = length[right[i]] = length[i] + 1;
// Print the leaves, i.e. for the alphabet symbols
    printf("   i  prob  parent  bits product  coden");
    for (i = 0; i < n; i++) {
        // Crawl up the tree to get prefix code
        outString[length[i]] = '';
        for (j = i; j != m - 1; j = parent[j])
            outString[length[j] - 1] = (left[parent[j]] == j) ? '0' : '1';
        printf("%5d %5.3f %5d %5d   %5.3f  %sn", i, priority[i], parent[i],
                length[i], priority[i] * length[i], outString);
        expected += priority[i] * length[i];
    }
    printf("Expected bits per symbol: %fn", expected);
// Print the internal nodes
    printf("   i  prob    left right parentn");
    for (i = n; i < m; i++)
        printf("%5d %5.3f %5d %5d  %5dn", i, priority[i], left[i], right[i],
                parent[i]);
    free(priority);
    free(left);
    free(right);
    free(parent);
    free(outString);
    free(length);
    free(pq);
    free(qp);
}

以下是一种方法：

（a）。您将希望每个堆条目与两个相邻 可以合并的子树。pqdelmin（）确定合并后 要申请，您将需要pqdelete（）丢弃不需要的候选人 （由于合并）和pqinsert（）包括新候选人（也 由合并产生）。处理促进。

，但我被困在测序和管理数组中。请帮助！

Answer 1

由于给出了每个符号的不同概率，您可以拥有一个包含a和z的节点，该节点应该与包含b和c的另一个节点合并。没有简单的订购非叶节点的方法，这在较高级别上变得越来越抽象。

无论如何；为了控制子树的顺序，合并节点时可以交换左右子树：

// Huffman code tree construction
for (i = n; i < m; i++) {
    left[i] = PQdelmin();
    right[i] = PQdelmin();
    if (CompareNodes(left[i], right[i]) > 0) {
        Swap(&left[i], &right[i]);
    }
    parent[left[i]] = parent[right[i]] = i;
    priority[i] = priority[left[i]] + priority[right[i]];
    PQinsert(i);
}

---

更多信息：

• 近似订单的霍夫曼代码（Stackoverflow）
• Antoshenkov等的命令保留密钥压缩。al。（PDF）