C++ Yeniden yığınlama işlemimde maksimum yığınta sorun nedir?

Question

Bu benim ilk stackexchange gönderiim, lütfen nazik olun :-) ben C++ kullanarak veri yapıları alan bir lisans öğrenciyim. Burada uygulamaya verildi başlık dosyasıdır (STL en yığın sınıfını kullanmak için izin, ama biz onun vektör sınıfını kullanabilirsiniz değil):

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 
}; 

I (özel bölümünde) bu yardımcı eleman fonksiyonunu

eklendi İşte

//template <typename T> 
void swap_up(const T& item, std::vector<int> v); 

insert fonksiyonunun benim uygulamasıdır:

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); 
    } 
} 

ben her şey yolunda zaten olup olmadığını swap_up işlevini çağırmalıdır değil biliyorum ama bu doğru NO endişelendirmiyor w. Bu işlevin içinde neler olduğuyla ilgileniyorum. İşte benim swap_up fonksiyonudur:

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; 
     } 
    } 
} 

Ve burada benim test kodu: Bu kodu çalıştırdığınızda

#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; 
} 

max anlamıyorum hep 40. yüzden, benim algoritması düşünüyorum Dengeli yığının sonundan doğru durma noktasına kadar hareket etmek için oldukça sağlamdır. Burada bir şey mi eksik? Şimdiden teşekkür ederim.

Answer 1

Sanırım sorunumu görüyorum. Her eklediğimde bunu yeni bir vektöre yapıyorum. Bu, orijinal vektörün neden her zaman en büyük değer olarak ilk değeri gösterdiğini açıklar - asla başka bir değer almaz! Heap.h adresindeki özel vektör değişkenine erişerek swap_up() işlevimi kullanmaya devam etmek için kodumu değiştirmek istiyorum ancak nasıl yapılacağını anlayamadım.