そこで、二分木の最小ヒープを作成しました。それをテストするために、2 つの異なる値を持つ一連のノードを作成します。
言う
struct node
{
int frequency;
int data;
}
ヒープが主にソートするのは頻度であるとしますが、ノードの頻度が同じ場合は、ノードのデータでソートします。
ノードの束を作成し、ヒープをロードし、それらをポップして印刷すると、取得します(サイズはツリー内のノードの数であり、最小は各ツリーが保持する最小データです)
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
気付かなかった場合は、3 番目のエントリが間違っているため、ヒープが間違っています。
私のバグは、minheap upheap downheap、remove、または insert のどこかにあります。
シムシティのような他の多くの楽しいことをするために、私は何日も試みてきましたが、私の脳はそれを処理できません。（そうでもない、私はこれを終わらせなければならない）
これが私のヒープです
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 クラスを作成する必要があることに言及する必要があります。頻度が同じ場合、ヒープはツリーに保持されている最小値で優先順位を選択することも想定されているため、コード内のミンキー ポインターはそのようになっています。正しい順序ではない理由を理解する必要があります。
私のプログラムはハフマン コーダー用です 。
ubuntu 64 システムでコンパイルする make ファイルがあります。入力にリダイレクトを使用します。
上記のヒープは
echo "Sally Sold Sea Shells By The Sea Shore" > input
./huff < input から取得されます