C++ sift down tas

Je suis en train d'écrire un programme qui nécessite d'utiliser un tas, et tout fonctionne bien en dehors de mes méthodes de tri, évidemment très important! Je ne suis pas sûr de ce qui ne va pas avec ma logique ou s'il me manque quelque chose de stupide. Mais une nouvelle paire d'yeux pour regarder ça serait bien.C++ sift down tas

La fonction est en train de passer mon vecteur qui est bien sûr le tas, l'emplacement de la racine, puis soit la STL soit moins ou plus grand comme prédicat.

template<class T,class P> 
void upheap(vector<T>& v, int start, P func) { 
    T x = v[start]; 
    while (start > 1 && func(x, v[start/2])) { 
     v[start] = v[start/2]; start /= 2; 
    } 
    v[start] = x; 
}

Une idée de ce qui ne va pas?

Source

2010-12-03 rajh2504

Vous dites que vous passez la racine du tas? Ne devriez-vous pas passer l'index de l'élément qui doit être amélioré? –

désolé ouais c'est ce que je voulais dire c'est la valeur de l'index. – rajh2504

Peut-être que vous devriez écrire les invariants, les pré-conditions et les post-conditions, et peut-être que vous verrez le problème. Par exemple, la condition 'HEAP (i = 0 .. start-1)' est-elle vraie à l'entrée? Et puis l'objectif est que la condition 'HEAP (i = 0..start)' soit vraie à la sortie? –

Le premier élément d'un vecteur est à v [0]. Vous semblez supposer que c'est à v [1]. Y a-t-il une raison à cela? Si la racine est à v [0], avec un nœud à l'indice i, le parent est à int ((i-1)/2) (bien que (i-1) >> 1 soit plus efficace) , et les enfants sont à 2i + 1, 2i + 2. Par exemple:

 0 
    1 2 
3 4 5 6 
78 9A BC DE

D'autre part, si la racine est à v [1], le parent est à l'int (i/2) (ou i >> 1), et les enfants sont à 2i, 2i +1 E.g .:

 1 
    2 3 
4 5 6 7 
89 AB CD EF

Cela pourrait donc être un problème.

Vous vérifiez si func (x, v [start/2]) est vrai. Si func est la condition du tas, vous pouvez vouloir vérifier si c'est faux ...

Le vecteur est-il déjà assez grand pour inclure v [start]? Si upheap() est utilisé pour ajouter des éléments dans le tas un par un ... Et la taille du vecteur n'est jamais augmentée ... (Aussi, vous commencez à v [1], pas à v [0]. Avez-vous essayé d'écrire un simple échafaudage (code utilisé pour tester/déboguer, mais qui ne fait pas partie du produit final) pour imprimer le tas, l'ajouter dans votre boucle, et courir avec Pratiquer des données pour voir où les choses se passent?

Source

2010-12-03 05:32:25

Répondre

Questions connexes