Domanda In che modo è possibile implementare std :: make_heap effettuando al massimo confronti 3N?


Ho esaminato lo standard C ++ 0x e ho trovato il requisito che make_heap non dovrebbe fare più di 3 * N confronti.

Cioè heapify Una raccolta non ordinata può essere eseguita in O (N)

   /*  @brief  Construct a heap over a range using comparison functor.

Perchè è questo?

La fonte non mi dà indizi (g ++ 4.4.3)

Il while (true) + __parent == 0 non sono indizi ma piuttosto un'ipotesi per il comportamento di O (N)

template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
{

  const _DistanceType __len = __last - __first;
  _DistanceType __parent = (__len - 2) / 2;
  while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
}

__adjust_heap ha l'aspetto di un metodo log N:

while ( __secondChild < (__len - 1) / 2)
{
    __secondChild = 2 * (__secondChild + 1);

È un log standard della tormenta per me.

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
          _Distance __len, _Tp __value, _Compare __comp)
    {
      const _Distance __topIndex = __holeIndex;
      _Distance __secondChild = __holeIndex;
      while (__secondChild < (__len - 1) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
          if (__comp(*(__first + __secondChild),
             *(__first + (__secondChild - 1))))
          __secondChild--;
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
          __holeIndex = __secondChild;
      }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
        *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             + (__secondChild - 1)));
        __holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, 
               _GLIBCXX_MOVE(__value), __comp);      
      }

Saranno apprezzati tutti gli indizi sul perché questo è <3N.
MODIFICARE:

Risultati sperimentali:

Questa implementazione reale utilizza

  • <2 N confronti per heap di heap
  • <1.5 N per l'heap di heap nell'ordine inverso.

28
2018-06-09 22:03


origine


risposte:


Un heap binario su n elementi può essere creato in tempo O (n) usando un algoritmo intelligente e un'analisi intelligente. Di seguito, parlerò di come funziona, supponendo di avere nodi espliciti e puntatori figlio destro e sinistro espliciti, ma questa analisi è ancora perfettamente valida una volta compresso in un array.

L'algoritmo funziona come segue. Inizia prendendo circa la metà dei nodi e trattandoli come un max-heap singleton - poiché c'è un solo elemento, l'albero che contiene solo quell'elemento deve essere automaticamente un max-heap. Ora prendi questi alberi e abbinali l'uno con l'altro. Per ogni coppia di alberi, prendi uno dei valori che non hai ancora usato ed esegui il seguente algoritmo:

  1. Rendi il nuovo nodo la radice dell'heap, con i suoi puntatori figlio sinistro e destro che si riferiscono ai due max-heap.

  2. Mentre questo nodo ha un bambino più grande di quello, scambia il bambino con il figlio più grande.

La mia tesi è che questa procedura finisce per produrre un nuovo heap massimo contenente gli elementi dei due max-heap di input, e lo fa nel tempo O (h), dove h è l'altezza dei due heap. La dimostrazione è un'induzione sull'altezza dei cumuli. Come caso base, se i subheap hanno dimensione zero, allora l'algoritmo termina immediatamente con un max-heap singleton, e lo fa in tempo O (1). Per la fase induttiva, supponiamo che per alcuni h, questa procedura funzioni su qualsiasi sottospecchio di dimensione h e consideri cosa succede quando lo esegui su due heap di dimensione h + 1. Quando aggiungiamo una nuova radice per unire due sottostrati di dimensioni h + 1, ci sono tre possibilità:

  1. La nuova radice è più grande delle radici di entrambi i sottoalberi. Quindi in questo caso abbiamo un nuovo max-heap, dal momento che la radice è più grande di qualsiasi nodo in entrambi i sottoalberi (per transitività)

  2. La nuova radice è più grande di un bambino e più piccola dell'altra. Quindi scambiamo la radice con il subchild più grande e ricorsivamente eseguiamo di nuovo questa procedura, usando la vecchia radice e i due sottoalberi del bambino, ognuno dei quali ha altezza h. Con l'ipotesi induttiva, ciò significa che il sottostruttura in cui ci siamo scambiati è ora un max-heap. Quindi l'heap complessivo è un max-heap, poiché la nuova radice è più grande di tutto ciò che è nella sottostruttura con cui abbiamo scambiato (poiché è più grande del nodo che abbiamo aggiunto ed era già più grande di tutto in quella sottostruttura), ed è anche più grande di tutto nell'altro sottoalbero (poiché è più grande della radice e la radice era più grande di tutto nell'altro sottoalbero).

  3. La nuova radice è più piccola di entrambi i suoi figli. Quindi, usando una versione leggermente modificata dell'analisi precedente, possiamo mostrare che l'albero risultante è effettivamente un heap.

Inoltre, poiché ad ogni passo l'altezza degli heap del bambino diminuisce di uno, il tempo di esecuzione complessivo per questo algoritmo deve essere O (h).


A questo punto, abbiamo un semplice algoritmo per creare un heap:

  1. Prendi circa metà dei nodi e crea cumuli singleton. (Puoi calcolare esplicitamente quanti nodi saranno necessari qui, ma è circa la metà).
  2. Abbina questi heap, quindi uniscili usando uno dei nodi inutilizzati e la procedura precedente.
  3. Ripetere il passaggio 2 finché non rimane un singolo heap.

Dato che ad ogni passo sappiamo che gli heap che abbiamo finora sono max-heap validi, alla fine questo produce un max-heap generale valido. Se siamo intelligenti con il modo in cui selezioniamo il numero di heap singoli, questo finirà per creare anche un albero binario completo.

Tuttavia, sembra che questo dovrebbe essere eseguito in tempo O (n lg n), poiché facciamo O (n) unioni, ognuna delle quali viene eseguita in O (h), e nel peggiore dei casi l'altezza degli alberi che stiamo unendo è O (lg n). Ma questo limite non è stretto e possiamo fare molto meglio essendo più precisi nell'analisi.

In particolare, pensiamo a quanto sono profondi tutti gli alberi che uniamo. Circa la metà degli heap ha profondità zero, quindi metà di ciò che rimane ha profondità uno, quindi metà di ciò che rimane ha profondità due, ecc. Se sommiamo questo, otteniamo la somma

0 * n / 2 + 1 * n / 4 + 2 * n / 8 + ... + nk / (2K) = Σk = 0⌈Log n⌉ (nk / 2K) = n Σk = 0⌈Log n⌉ (k / 2k + 1)

Questo limite superiore è il numero di scambi effettuati. Ogni scambio richiede al massimo due confronti. Pertanto, se moltiplichiamo la somma di cui sopra per due, otteniamo la seguente sommatoria, che limita il numero di swap effettuati:

n Σk = 0 (k / 2K)

La somma qui è la somma 0/20 + 1/21 + 2/22 + 3/23 + .... Questa è una famosa sommatoria che può essere valutata in diversi modi. Un modo per valutare questo è dato in queste diapositive di lezione, diapositive 45-47. Finisce per uscire esattamente a 2n, il che significa che il numero di confronti che finiscono per essere realizzato è sicuramente limitato da 3n.

Spero che questo ti aiuti!


52
2018-06-09 22:26



@templatetypedef ha già dato una buona risposta perché il tempo di corsa asintotico di build_heap è Sopra). C'è anche una prova nel capitolo 6 di CLRS, 2a edizione.

Per quanto riguarda il motivo per cui lo standard C ++ lo richiede al massimo 3n i confronti sono usati:

Dai miei esperimenti (vedi codice sotto), sembra che in realtà meno di 2n i confronti sono necessari Infatti, queste note di lezione contenere una prova build_heap usa solo 2 (n-⌈log n⌉) confronti.

Il limite dallo standard sembra essere più generoso di quanto richiesto.


def parent(i):
    return i/2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def heapify_cost(n, i):
    most = 0
    if left(i) <= n:
        most = 1 + heapify_cost(n, left(i))
    if right(i) <= n:
        most = 1 + max(most, heapify_cost(n, right(i)))
    return most

def build_heap_cost(n):
    return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))

Alcuni risultati:

n                     10  20  50  100  1000  10000
build_heap_cost(n)     9  26  83  180  1967  19960

17
2018-06-11 00:05