Kopiec [HEAP]

[j4rooo]

Mam problem z zadaniem kopiec: http://pl.spoj.com/problems/HEAP/

Budując kopiec z kolejnych elementów tablicy z wejścia i bazują na np. Elementarzu Chakiera (kolejki priorytetowe: http://students.mimuw.edu.pl/~szreder/skrypt.pdf) otrzymujemy inne wartości w tablicach niż wymagane w zadaniu:

-14 -11 -5 -8 1 -3 6 15 3 13
zamiast
-14 -11 -5 -8 1 -3 6 3 15 13

i

-18 -17 -14 -8 -4 -10 0 7 6 -1
zamiast
-18 -17 -14 -8 -4 -10 0 6 -1 7

W komentarzach pod zadaniem jest link do niedziałającego forum i, jak mi się wydaje, nieprzydatna podpowiedź:

Kopiec z gotowej tablicy można zbudować ‘w górę’ albo ‘w dół’. W zadaniu wymagana jest podejście ‘w dół’.

Próbując zmienić podejście budowania kopca moje wyniki zaczynając jeszcze bardziej odbiegać od oczekiwanych.

To wszystko sprowadza się do jednego: czy odnalezienie sposobu tworzenia przez autora kopca to sens tego zadania czy jednak mogę liczyć na wskazówki?

[tarpauwatratar]

O ile pamiętam trzeba to samemu wymyślić. Zdaje się, że 2 lata temu nie znałem tworu o nazwie kopiec i korzystałem z info na stronie: http://eduinf.waw.pl/inf/alg/001_search/0113.php + przykładu z http://www.coderscity.pl/ftopic30575.html i jakoś to ogarnąłem. Niestety, swojego rozumowania już nie odtworzę… Nie wiem, na ile to pomoże, ale:

1. heapify wołam rekurencyjnie w następujący sposób: wczytuję dane do tablicy, robię heapify(x) dla x = liczba węzłów / 2 i tak aż dojdę do korzenia (czyli dla 10 węzłów robię heapify(5), heapify(4), …, heapify(korzeń) w pętli while). Analogicznie wołam heapify po usunięciu korzenia
2. nie używam wskaźników, mam globalną zmienną na ilość węzłów i funkcje pop() oraz heapify(). Kopiec to u mnie int heap[size];
3. heapify(int node) opieram na warunkach typu if(left <= nodes && heap[left] < heap[min]) i analogicznie dla right. Jeśli syn jest mniejszy od danego węzła - swap i heapify(syn)

Celowo piszę w miarę niejasno, aby nie dać gotowca, ale jak będzie Ci potrzebny to priv

Poniżej kopia przykładu z coderscity, ale z pominięciem kolorów.

Wejście:
3
-14
-3
15
13
-5
6
-8
-11
1

Po wpisaniu do tablicy...

                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-3)------.
        ,-(15)-.         ,-(13)              (-5)               (6)
     (-8)      (-11)   (1)
   
"Ukopcowanie":

                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-3)------.
        ,-(15)-.         ,-(13)              (-5)               (6)
     (-8)     (-11)    (1)


                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-3)------.
        ,-(15)-.         ,-(1)               (-5)               (6)
     (-8)      (-11)   (13)


                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-3)------.
        ,-(-11)-.        ,-(1)               (-5)               (6)
     (-8)       (15)   (13)


                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-5)-----.
        ,-(-11)-.        ,-(1)               (-3)              (6)
     (-8)       (15)   (13)


                     ,---------------(3)--------------.
             ,----(-14)----.                    ,-----(-5)-----.
        ,-(-11)-.        ,-(1)               (-3)              (6)
     (-8)       (15)   (13)


                     ,--------------(-14)-------------.
             ,-----(3)-----.                    ,-----(-5)-----.
        ,-(-11)-.        ,-(1)               (-3)              (6)
     (-8)       (15)   (13)


                     ,--------------(-14)-------------.
             ,----(-11)----.                    ,-----(-5)-----.
        ,--(3)--.        ,-(1)               (-3)              (6)
     (-8)       (15)   (13)

                     ,--------------(-14)-------------.
             ,----(-11)----.                    ,-----(-5)-----.
        ,-(-8)--.        ,-(1)               (-3)              (6)
      (3)       (15)   (13)

[mariusz193]

nie sądzę, aby trzeba było to samemu wymyślić

patrzę na kod i nic nie rozumiem - więc pewnie pisałem na podstawie jakiegoś wzorca, i to właściwego bo zaliczyłem zadanie za pierwszy razem

[j4rooo]

Celowo piszę w miarę niejasno, aby nie dać gotowca, ale jak będzie Ci potrzebny to priv

W którym miejscu jest niejasno? Bardzo dobrze wytłumaczone.

W zadaniu trzeba zwrócić uwagę, na to, że autorowi chodzi o zbudowanie kopca w miejscu, a nie przepisywaniu wejścia element po elemencie do drugiej tablicy. Wtedy faktycznie kopiec wychodzi taki jak sobie zażyczył.