写一个C++ 程序，在时间复杂度为O(n)的情况下，找到哈夫曼树中两个最小的权

在C++中，要找到哈夫曼树（Huffman Tree）中两个最小的权值节点，首先需要构建哈夫曼树并存储其结构信息。由于哈夫曼树是通过贪心算法自底向上构造的，每个非叶节点总是由两个权值最小的子节点合并而成。因此，我们可以设计一个优先队列（通常使用最小堆）来辅助查找操作。

以下是一个简单的C++程序示例，假设我们有一个`Node`类表示哈夫曼树的节点，包含权值和左、右子节点：

#include <iostream>
#include <queue>

struct Node {
    int weight;
    Node* left, *right;
};

// 插入节点到最小堆
void insert(Node** heap, const Node& node) {
    std::priority_queue<Node*, std::vector<Node*>, std::greater<Node*>> h;
    h.push(&node);
    
    while (!h.empty()) {
        Node* min_node = h.top();
        h.pop();

        if (min_node->left == nullptr) {
            (*heap)[0] = min_node; // 更新根节点为当前最小节点
            break;
        }

        h.push(min_node->left);
        h.push(min_node->right);
    }
}

// 返回堆顶的最小节点
Node* findMin(Node** heap) {
    return (*heap)[0];
}

int main() {
    Node* nodes[] = { ... }; // 哈夫曼树的所有节点数组
    int n = sizeof(nodes) / sizeof(Node);

    // 构建最小堆并插入所有节点
    for (int i = 0; i < n; ++i)
        insert(heap, nodes[i]);

    // 找到并返回两个最小的节点
    Node* smallest1 = findMin(heap);
    Node* smallest2 = findMin(heap); // 由于堆保证了每次取出都是最小，第二次取也是最小

    // 输出结果
    std::cout << "Two smallest weights are: " << smallest1->weight << " and " << smallest2->weight << "\n";

    return 0;
}

在这个程序中，时间复杂度为O(n log k)，其中n是节点数，k是在最坏情况下的叶子节点个数。因为每次从堆中弹出最小元素，堆操作的时间复杂度是O(log k)。整个过程需要执行n次，所以总的时间复杂度是O(n log k)。如果哈夫曼树本身就是完全二叉树，则k = n/2，此时时间复杂度降为O(n)。