用优先队列求哈夫曼树的权值和，出现指针改变问题

Question

为什么这个优先队列会改变我的树节点的left和right指针值？

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出权值。

输入样例#:
5
1 2 2 5 9

输出
37

//
//  哈夫曼树.cpp
//  计算机复试
//
//  Created by owenjiang on 2023/3/13.
//
#include<iostream>
#include<queue>
using namespace std ;
typedef struct Node{
    int value ;
    Node *left, *right ;
} *Node2;
bool operator < ( Node node1,Node node2){
    return node1.value > node2.value ;
}
Node* createNode(int val){
    Node *node = new Node() ;
    node->left = NULL ;
    node->right = NULL ;
    node->value = val ;
    return node ;
}
void caculate(Node *root,int height,int &result){
    if (root->left == NULL && root->right == NULL) {
        result += height * root->value ;
        return ;
    }
    caculate(root->left, height+1, result) ;
    caculate(root->right, height+1, result) ;
}
int createHalfManTree(priority_queue<Node> &nodesValue){
    while (nodesValue.size() > 1 ){
        Node *newNode = new Node() ;
        Node topOne = nodesValue.top() ;
        nodesValue.pop() ;
        Node topTwo = nodesValue.top() ;
        nodesValue.pop() ;
        newNode->value = topOne.value + topTwo.value ;
        newNode->left = &topOne ;
        newNode->right = &topTwo ;
        nodesValue.push(*newNode) ;
    }
    Node root = nodesValue.top() ;
    int result = 0 ;
    caculate(&root,0,result) ;
    return result ;
}
int main(){
    int nodes;
    while (cin >> nodes){
        priority_queue<Node> heap ;
        int temp ;
        for (int i=0;i<nodes;i++){
            cin >> temp ;
            heap.push(*createNode(temp)) ;
        }
        int weight = createHalfManTree(heap) ;
        cout << weight << endl ;
    }
    return 0 ;
}

```

Answer 1

一个优先队列可以用二叉搜索树来实现，其中每个节点有一个值和一个左右指针。插入和删除操作会根据值的大小来调整树的结构，从而改变节点的左右指针。例如，如果要删除一个节点，而它有一个左子树，那么就需要把它的父节点的右指针指向它的左子树1。

如果你想了解更多关于优先队列和二叉搜索树的知识，你可以参考以下链接：

1 https://codereview.stackexchange.com/questions/124200/priority-queue-binary-search-tree-implementation
2 https://www.geeksforgeeks.org/implement-the-insert-and-delete-functions-on-priority-queue-without-array/
3 https://www.geeksforgeeks.org/right-view-binary-tree-using-queue/
希望这对你有帮助。🙏