Varför heapbygge vid en närmare undersökning har komplexiteten O(n)
-------------------------------------------------------------------

Komplexiteten O(nlogn) får man om man litet grovt antar att varje element ska
bubbla genom en stor del av trädet. En noggrannare analys kan se ut så här.

Utgå från ett binärt träd med den här strukturen:

              7
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      6               5
     / \             / \
    /   \           /   \
   /     \         /     \
  4       3       2       1
 / \     / \     / \     / \
·   ·   ·   ·   ·   ·   ·   ·

OBS! Talen är bara en numrering av den ordning i vilken vi kommer att gå igenom
noderna, det är inte dom aktuella värdena som lagras i heapen.

För att återställa heapordningen går vi igenom trädet nivå för nivå från löven
till roten. Dvs om trädet representeras i en array går vi från högsta till
lägsta index.

På lövnivån behöver ingenting göras efersom ett ensamt löv är en korrekt heap.

Talen i noderna 1-4 kan behöva flyttas ner ett steg. Antag för enkelhets skull
att det alltid är ner till vänster. Då berörs dom "*"-markerade bågarna i:


              7
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      6               5
     / \             / \
    /   \           /   \
   /     \         /     \
  4       3       2       1
 * \     * \     * \     * \
·   ·   ·   ·   ·   ·   ·   ·

Sen är det dags för nod 5-6. Där kan det ju faktiskt råka vara så att talen där
behöver flyttas ner 2 steg, ända till löven. Antag att förflyttningen sker ett
steg ner till vänster, därefter till höger, för att vad som händer ska synas i
den här figuren, där nya "*"-bågar har tillkommit:

              7
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      6               5
     * \             * \
    *   \           *   \
   *     \         *     \
  4       3       2       1
 * *     * \     * *     * \
·   ·   ·   ·   ·   ·   ·   ·

Osv mot roten där till sist rotnoden kan behöva flyttas ända till ett löv - ett
steg ner till vänster, därefter nedåt höger till ett löv:

              7
             * \
            *   \
           *     \
          *       \
         *         \
        *           \
       *             \
      6               5
     * *             * \
    *   *           *   \
   *     *         *     \
  4       3       2       1
 * *     * *     * *     * \
·   ·   ·   ·   ·   ·   ·   ·

Hur många byten kan ha skett, hur många "*"-bågar finns i det sista trädet?

Hur många bågar finns totalt?
Varje nod har en båge till sin förälder, utom rotnoden. Alltså finns det n-1
bågar totalt i trädet. Dom som kommer att vara omarkerade efter den här
proceduen är vägen från roten till sista lövet, h st., där h=trädets höjd.

Antal bubblingssteg blir alltså O(n-1-h)=O(n), eftersom h<n