0
これは私の最初のスタックエクスチェンジポストですので、穏やかにしてください:-)私は、C++を使ってデータ構造をとっている学部生です。ここでは、（STLのヒープクラスを使用することはできませんが、私たちはそのベクトルクラスを使用することができます）を実装するために与えられたヘッダファイルは次のとおりです。C++最大ヒープでの私の再疎結合処理で何が問題になっていますか？
template <typename T>
class heap
{
public:
heap();
// postcondition: empty heap has been created
unsigned int size() const;
// postcondition: number of elements in a heap has been returned
bool is_empty() const;
// postcondition: returned whether the heap is empty
void insert (const T& item);
// postcondition: item has been added
void remove();
// precondition: heap is not empty
// postcondition: largest item has been removed from the heap
T max() const;
// precondition: heap is not empty
// postcondition: copy of largest element in the heap has been returned
T& max();
// precondition: heap is not empty
// postcondition: access to largest element in the heap has been returned
private:
std::vector<T> v;
unsigned int max_child (unsigned int index) const;
// precondition: element at index has children
// postcondition: index of the larger child has been returned
// if there is only 1 child - index of that child has been returned
};
私は
（プライベートセクションで）このヘルパーメンバ関数を追加しましたここで//template <typename T>
void swap_up(const T& item, std::vector<int> v);
はinsert関数の私の実装です：
template <typename T>
void heap<T>::insert (const T& item)
// postcondition: item has been added
{
v.push_back(item);
if(v.size() > 1){
swap_up(item, v);
}
}
私はすべてのためにすでにある場合、私はswap_up関数を呼び出すべきではありませんけど、私はその権利がない心配していませんよw。私はその機能の中で起こっていることに懸念しています。ここに私のswap_up機能は次のとおりです。
template <typename T>
void heap<T>::swap_up(const T& item, std::vector<int> v){
unsigned int index = v.size()-1;
unsigned int parent_index = (index-1)/2;
//unsigned int value;
T value;
while(item > v[parent_index]){
//if(item > v[parent_index]){
value = v[parent_index];
v[parent_index] = item;
v[index] = value;
//}
if(parent_index > 0){
index = parent_index;
parent_index = (index-1)/2;
}
}
}
そしてここでは、私のテストコードは次のとおりです。
#include <iostream>
#include "heap.h"
//#include "priority_queue.h"
using namespace std;
int main() {
heap<int> h1;
h1.insert(40);
h1.insert(50);
h1.insert(60);
h1.insert(70);
h1.insert(80);
int max = h1.max();
cout << "The max is " << max << endl;
return 0;
}
私はこのコードを実行すると、最大は私が私のアルゴリズムだと思うように私は、理由を理解していない、常に40です。バランスの取れたヒープの終わりから適切な停止点がかなり安定するまで移動するためのものです。私はここに何かを逃していますか前もって感謝します。