[C++] ShiftUp in un Heap Tree

[Ippo343]

Ciao a tutti,

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

Questa implementazione ha il seguente metodo ShiftUp:

// 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?

    5
7      3

Dopo lo shift, diventa:

    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:

[YuYevon]

Innanzitutto, chi ha scritto quel codice cosa aveva intenzione di creare? Un min-heap o un max-heap? Ossia, un heap in cui, ad ogni livello, il padre risulti minore dei figli o, al contrario, un heap in cui il padre sia sempre maggiore dei figli? Dal codice che ho letto mi sembra che voglia costruire un max-heap, e comunque l'esempio che hai fatto non è corretto perché secondo quel codice lo scambio avviene quando il padre ha valore minore del figlio(if Data[Parent] < Item), non viceversa, quindi in questo caso

      5
7          3

non avverrebbe alcuno shift, perché 5 (il padre) è maggiore di 3.

Semplicemente quel metodo serve a mantenere la proprietà dell'heap (supponendo quindi che si tratti di un max-heap): se ad un certo livello dell'albero il padre risulta essere minore di un figlio, viene shiftato con questo, e l'effetto risulta essere appunto uno "shift up" (una salita) del figlio nei livelli dell'albero.

[Ippo343]

Ok, il suo è un max heap. Ma in ogni caso, per essere ordinato un heap non dovrebbe avere le "foglie" in ordine?

Intendo, il nodo sinistro non dovrebbe essere sempre minore del nodo destro (o maggiore se è un max-heap?)

[YuYevon]

No, le proprietà degli heap nulla impongono sull'ordinamento relativo dei nodi figli.

Da Wikipedia

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). Also the tree data structure must be a complete tree for satisfying the heap property. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.)

Quindi un heap, per essere tale, deve soddisfare come unica proprietà quella che ti dicevo, e cioè ogni nodo deve essere maggiore (o minore, nel caso di un min-heap) dei due figli, poi quale relazione vi sia tra questi è irrilevante.

Forse stai facendo un po' di confusione con gli Alberi Binari di Ricerca (ABR, o BST "Binary Search Tree", non so come li chiami), che prevedono come proprietà che ogni nodo abbia come figlio sinistro un nodo minore e come figlio destro uno maggiore.

Comunque gli heap in realtà avrebbero anche altre due proprietà, che però non c'entrano nulla con l'ordinamento delle foglie:

1) tutte le foglie hanno profondità h o h - 1, dove h è l'altezza dell'albero;
2) tutti i nodi interni hanno grado 2, eccetto al più uno.

Ovviamente parliamo di heap binari.

[Ippo343]

Mmm ok grazie. Ciao!