Sortowanie przez kopcowanie

[paula.0120]

Witam. Ostatnio zainteresował mnie temat kopców oraz sortowania przez kopcowanie.
Przy zastosowaniu HEAPSORT napotkałam się z pewnym problemem. Moja tablica zawiera przypadkowe liczby, przy czym niektóre się powtarzają. Przy budowaniu kopca typu max moja dwójka dzieci znajdująca się bezpośrednio przy korzeniu ma takie same wartości. Czy mógłby mi ktoś powiedzieć jak w takich wypadkach postępować? Dodatkowo HEAPSORT powinno zwracać mi posortowaną tablice, ale również nie wiem jak to powinno wyglądać przy powtarzających się cyfrach. Bardzo proszę o jakieś wskazówki.

[Jan_J]

A radzisz sobie z prostszymi metodami sortowania?

[paula.0120]

Tak Nie mam z nimi żadnego problemu.

[paula.0120]

Wiem, że wszystkie elementy zostaną wywołane w kolejności od największej do najmniejszej. Ale chciałabym wiedzieć, jeżeli moja dwójka dzieci przy korzeniu są takie same, to które z nich (prawe czy lewe) powinno wyskoczyć jako pierwsze na miejsce korzenia? Czy ta kolejność ma jakieś znaczenie? Bo gdybym miała to zrobić to najpierw wzięłabym wyraz po lewej stronie.

[Jan_J]

W sortowaniu stogowym wartości z nieuporządkowanej części są po kolei wstawiane w kopiec.
Przebudowa kopca spowodować może, że wpisy o tej samej wartości utracą swoją wzajemną pozycję.
To znaczy, ciąg wynikowy będzie uporządkowany, ale bez gwarancji zachowania pierwotnej kolejności elementów równych. O takich metodach sortowania mówi się, że są niestabilne.

[paula.0120]

Super. Zrozumiałam kwestię teoretyczną
Chciałabym to teraz przełożyć na Pythona.
Po wpisaniu dowolnej listy chciałabym, żeby program sprawdzał mi czy dana lista jest kopcem typu max.
Czy mogłabym poprosić o jakieś wskazówki od czego zacząć?
Oczywiście zdefiniowałam na początek :

def heap_parent(n) :
return (n-1)/2
def heap_left(n) :
return (2*n+1)
def heap_right(n) :
return (2*n+2)
Wiem, że listy w Pythonie indeksowane są od 0. Mam nadzieję, że dobrze zdefiniowałam podane funkcje

[Jan_J]

Długo nie odpisywałem; jest trochę dodatkowej roboty w czasie epidemii.

W kopcu typu max każdy węzeł przechowuje wartość większą lub równą niż wszystkie węzły leżące pod nim w sensie porządku drzewa. Natomiast nie ma wymagań co do porządku rodzeństwa.

Heapsort ma w sobie sprytne założenie: na jedną strukturę patrzymy dwojako – albo jak na tablicę/listę, albo jak na drzewo/kopiec binarny zrównoważony. Wobec tego warto przyjąć konwencję: pierwszy element tablicy to górne piętro kopca; nastęne 2 elementy to piętro drugie (od góry), następne 4 to piętro trzecie, itd. Da się tak, bo nieobsadzone pozostać mogą co najwyżej pewne pozycje końcowe w piętrze na samym dole.
W takim układzie drzewo (nieco krzywo naszkicowane;)

Kod: Zaznacz cały

                               a
                        /              \
                   b                         c
                 /     \                  /     \
              d           e             f          g
           /    \       /    \        /    \     /    \
          h      i     j      k      l     m    n      o  

będzie zakodowane w tablicy

Kod: Zaznacz cały

wartości: a  b  c  d  e  f  g  h  i  j  k  l  m  n  o
indeksy:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
                ^-----------'
                            p

z czego wynika, że – przy umowie numerowania od 0 – każdy element (nr p) jest bezpośrednim potomkiem elementu o numerze (p-1) div 2. Na przykład, jak na szkicu: element nazwany g znajduje się w tablicy pod numerem 6, więc leży bezpośrednio pod elementem o numerze (6-1) div 2 = 2, równym c.

Dla sprawdzenia czy lista/tablica jest kopcem, wystarczy przejrzeć ją indeks po indeksie; mając bieżący indeks patrzymy na element nadrzędny i porównujemy ich wartości. Np. w taki sposób

Kod: Zaznacz cały

def has_heap_ordering(a):
    ' czy tablica / lista a jest kopcem typu max '
    n = len(a)
    for i in range(1,n):
        if a[(i-1)//2] < a[i]:
           return False
    return True

albo – gdyby uwolnić się od dogmatu, że problem decyzyjny musi dawać odpowiedź boolowską:

Kod: Zaznacz cały

def has_heap_ordering(a):
    ''' sprawdza czy tablica / lista a jest kopcem typu max.
    wynik: 
        dodatni – numer pierwszego znalezionego węzła większego od rodzica; 
        0 – porządek kopca jest zachowany.
   '''
    n = len(a)
    for i in range(1,n):
        if a[(i-1)//2] < a[i]:
           return i
    return 0

(W przypadku heapsort nie ma potrzeby takiego sprawdzania, gdyż kopiec buduje się dołączając do niego element po elemencie.)

[paula.0120]

A gdybym chciała usunąć dowolny element z mojej listy, tak żeby po tym mój kopiec wracał do typu max. Jak wyglądała by taka funkcja, gdybym chciała użyć heapifty? Mogłabym prosić o jakieś wskazówki?

[Jan_J]

A co to jest heapfity?
I dlaczego akurat heapfity, a nie kukubojaniewiemco?

Ja bym się skupił na zrozumieniu co to znaczy usunąć w liście (w miarę proste) i usunąć w drzewie/kopcu; jak usunięcie wpłynie na patrzenie na kopiec. Próbowałbym wyobrazić sobie raczej nie tyle fizyczne usunięcie (na to szkoda energii, bo potem trzeba reindeksować), tylko żeby wykorzystać miejsce zwalniane przez usuwany element. Dobre ćwiczenie na narysowanie sobie diagramów, co ma gdzie wskakiwać – jeśli istnieje bezpośrenie potomstwo to któreś z nich, i co dalej? Bo proste usunięcie węzła naruszy zrównoważenie. A potem trzeba to przeskakiwanie opisać w języku listy.

To: https://eduinf.waw.pl/inf/alg/001_search/0113.php jest pierwszorzędny materiał dydaktyczny opracowany przez nauczyciela z LO w Tarnowie, pana Jerzego Wałaszka. Warto też odwiedzić zasoby Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (łoj, jak to się długo pisze – mimuw): http://wazniak.mimuw.edu.pl/index.php?t ... ury_danych. A głębiej, to chyba już w podręcznikach algorytmów i struktur danych. Z cieńszych, polskich: Piotr Wróblewski, Algorytmy, struktury danych i techniki programowania, Helion 2015.