所以我做了一小堆二叉树。为了测试它，我创建了一堆具有 2 个不同值的节点。
说
struct node
{
int frequency;
int data;
}
说频率是堆主要排序的，但是如果节点频率相同，那就是按照节点数据排序。
当我制作一堆节点并加载堆并弹出并打印它们时，我得到了（大小，是树中有多少节点，min是每棵树拥有的最小数据）
Data Freq Size Min
10 1 1 10
84 1 1 84
115 1 1 115
66 1 1 66
114 1 1 114
100 1 1 100
121 2 1 121
111 2 1 111
104 3 1 104
97 3 1 97
101 5 1 101
108 5 1 108
83 6 1 83
32 9 1 32
如果你没有注意到，第三个条目是错误的，因此堆是错误的。
我的错误位于 minheap upheap downheap 的某个地方，删除或插入。
我已经尝试了好几天，我的大脑无法处理它，还有很多其他有趣的事情要做，比如模拟城市。（不是真的，我必须完成这个）
这是我的堆
class MinHeap
{
public:
int length;
MinHeap(int mVal );
~MinHeap();
int size(); // returns N, the size of the heap
void insert(node* e);
node* remove();
void printheap();
private:
node **a; // Array of pointers
int MaxSize;
int N; // current size of heap
int itemMin;
void upheap(int k);
void downheap(int k);
};
MinHeap::MinHeap(int mVal)
{
a = new node*[mVal+1](); // a** is an array of pointers;
N=0; // Sets heap size to zero
a[0]= new node();
length = mVal+1;
MaxSize = mVal;
itemMin = -32767; // Minimum Heap
a[0]->frequency= itemMin ;
}
MinHeap::~MinHeap()
{ delete [] a;}
void MinHeap::upheap(int k)
{
node *e = a[k] ;
while( e->frequency < a[k/2]->frequency )
{
a[k] = a[k/2] ; //move parent down
k = k/2 ;
}
while(e->frequency == a[k/2]->frequency && e->minkey < a[k/2]->minkey)
{
a[k] = a[k/2] ; //move parent down
k = k/2 ;
}
a[k] = e ;
}
void MinHeap::downheap(int k)
{
int j = 2 * k ;
node *e = a[k] ;
while (j <= N) {
if ((j < N) && (a[j+1]->frequency < a[j]->frequency)) j++ ;
if((j<N) && (a[j+1]->frequency == a[j]->frequency) && (a[j+1]->minkey > a[j]->minkey ))j++;
if (( e->frequency <= a[j]->frequency) ) break;
a[j/2] = a[j]; // move child up
j *= 2; // move child down a level
}
a[j/2] = e;
}
void MinHeap::insert(node* e)
{
a[++N] = e ;
upheap(N) ;
}
node* MinHeap::remove()
{
node *e = a[1];
a[1] = a[N--]; downheap(1) ;
return &(*e);
}
我应该提一下，我需要创建自己的 STL 类，如果频率相同，堆也应该选择优先级，其中树中保存的最小值是相同的，所以这就是代码中的 minkey 指针。只需要弄清楚为什么它的顺序不正确。
我的程序适用于霍夫曼编码器，这里是： 我的文件
它有一个在 ubuntu 64 系统上编译的 make 文件。使用重定向输入。
上面的堆来自
echo "Sally Sold Sea Shells By The Sea Shore" > input
./huff < input