Ciao a tutti,

stavo studiando gli heap tree e mi sono imbattuto in un dubbio curioso.

Questa implementazione ha il seguente metodo ShiftUp:

codice:
// ShiftUp() function
template <class Elem>
void HeapTree<Elem>::ShiftUp(int Node)
{
  int  Current = Node,
       Parent  = ParentOf(Current);
  Elem Item    = Data[Current];

  while (Current > 0)  // While Current is not the RootNode
  {
    if (Data[Parent] < Item)
    {
      Data[Current] = Data[Parent];
      Current = Parent;
      Parent = ParentOf(Current);
    }
    else
      break;
  }
  Data[Current] = Item;
}
Ora, se non erro, nel caso il nodo figlio sia minore del suo padre, allora i due vengono scambiati. E fin qui ok. Al che mi è venuto un dubbio: il nodo padre ha un indice minore di entrambi i suoi figli, in un heap. Perciò se il figlio ha un indice minore va ovviamente scambiato col padre. Ma se questo nodo figlio fosse il figlio destro? Otterrei che dopo lo scambio il nodo sinistro ha un indice maggiore del nodo destro, e quindi l'albero non è più ordinato, sbaglio?

codice:
    5
7      3
Dopo lo shift, diventa:

codice:
    3
7      5
E quindi non è più ordinato...

Al che: è un caso che andrebbe gestito e che non è gestito in quel codice che ho letto... o semplicemente mi sfugge qualcosa sugli heap!? :master: