Matematické Fórum

↑ VojtechSejkora:

Pokud se nepletu, tak to máš z téhle stránky: http://ksp.mff.cuni.cz/tasks/20/cook4.html Je u toho i obrázek, který mi přijde celkem jasný. Ten ti nepomohl?

Vlastními slovy to řeknu takto. Máš nějaký vrchol a k němu náleží dva potomci. Ovšem číselné označení vrcholů je inkrementující zprava doleva, takže pokud se chceš posunout na potomka, tak musíš přeskočit všechny ostatní vrcholy na stejné úrovni. Asi je to trochu kostrbatě řečené, ale snad ti to trochu pomůže.

Má dva následníky, protože je to prostě výhodné z hlediska časové náročnosti. Jak se na té stránce píše, tak se halda využívá například ke třídění čísel.

A ano, pro k=10 budou následníci na pozicích 20 a 21.

Co se týče tvého druhého dotazu, tak to prostě souvisí s uspořádáním té haldy. Koukni se na uvedený obrázek a a na tento algoritmus (je také na té stránce):

procedure vloz(prvek: integer);    
var i, x: integer;
begin
  i:=N; N:=N+1;
  halda[i]:=prvek;
  while (i>1) and (halda[i div 2]>halda[i]) do begin
    x:=halda[i div 2];
    halda[i div 2]:=halda[i];
    halda[i]:=x;
    i:=i div 2
  end
end;

Jak vidíš, tak prohazuješ prvek s jeho předchůdcem tak dlouho, dokud buď neprobublá na první pozici haldy, nebo dokud je jeho předchůdce větší.

↑ pizet:

díky tak tomu teď už trošku rozumím.... mě nedošlo že to musím brát pro ten blbej strom.... a kde se dá najít něco o binárním stromě?

ano řeším KSP, a myslel jsme že budu toto potřeboval, ale jesli jsem to tedy dobře pochopil tak ten binární strom je realizován v poli?

a jakto že na 3.pozici není 7čka a je tam 20tka?:-o.... ano splňuje podmínky haldy, ale.....pokud bych to měl tedy v poli tak by to bylo špatně seřazeno když to chci mít od nejnižšího po nejvyšší a nebo to já takto seřazeno nechci? a nebo to se dělá až v tom dalším? a tady se spokojím jen s tím že předešlý prvek je menší než tento a následovník je větší?

jinak 1čka je jasná, protože je to normální binární soustava, tu znám ze školy , 2ku taktéž chápu a 3ku taky.... takže pokud jen tyto 3body musím splnit pro haldu.... tak si nastuduji binární strom a potom heap nebo jak se jmenuje to seřazování pomocí haldy.... díky asi jsme to trošku pochopil:)

↑ septolet:
ano mám to z kuchařky a asi i zu toho serveru jak jsi psal, ale koukal jsme se na to i na wiki, ale ta mi vůbec nepomohla a ono když máme programování 1.ročník a já bych tomu ani programování neříkal (pomalu toho i já vím více jak p. učitel, ale něco ví on zas já)  tak nemůžu vědět co je to binární strom... navíc se stejně v tom programování učíme jen psaní nějakých blbostí podle předem napsaného algoritmu takže vpodstatě přepisujeme grafický algoritmus do jazyka java...takže nic moc

jo a paskalu vůbec nerozumím a nevyznám se v něm ano měl bych se ho asi doučit, protože většina věcích obecných je psaná v paskalu, ale prostě mě zatím tneto jazyk nedává moc smysl a neumím ho číst, proto mi byl ten obrázek kničemu

↑ VojtechSejkora:

Ahoj, je to jednoduchý, jenom je potřeba si uvědomit pár věcí...
Je dobrý vědět, co to je binární strom. Je to datová struktura, kterou vidíš na obrázkách. Máš nějakej uzel a ten má maximálně dva poduzly (proto se mu taky říká binární). Jak vidíš, tak ty uzly úplně dole už nemají žádný poduzly a říká se jim listy stromu.

Jak takovouhle strukturu implementovat? Normálně se to implementuje pomocí ukazatelů. Uděláš si datový typ záznam (když to budeš psát třeba v Pascalu), kde budeš mít užitečnou hodnotu - to je obsah toho uzlu a pak dva ukazatele, každej na jeden poduzel.
Jiná možnost je implementovat to pomocí pole a to je právě to co máš dělat ty.
Abysme se v tom nezamotali tak budem rozlišovat dva pojmy: Předchůdce v poli je prvek s indexem o jedničku menším. Takže předchůdce v poli prvku s indexem 5 je prvek s indexem 4. Toto tě ale vůbec nezajímá... Předchůdce v haldě je rodič danýho prvku v binárnim stromu. Takže když koukneš na ty obrázky, tak předchůdce v haldě prvku 10 je prvek 5. NENÍ to prvek 9 ani 8 atd atd.


Aby to bylo jednodušší na pochopení, tak pole indexuju od 1 a na začátku do něj dám prvky stejný jako jsou jeho indexy. Takže je hezky vidět, že je ten strom v tom poli uloženej jakoby po řadách...

Teď si představ, že do týhle struktury chceš vložit prvek s hodnotou 2,5. Tak jak to ukazuje další obrázek.


Ty chceš tenhle prvek vložit na správný místo v poli. Takže tak jak to máš napsaný v tom návodu ho na začátku vrazíš na konec pole. Dobrý je ale tady si uvědomit, kdo je předchůdce v hromadě tohodle prvku. Není to 15tka, ale je to 8čka!!! tak jak to je nakreslený na obrázku. Index předchůdce spočítáš pomocí trunc(k/2) viz ten tvůj návod.

Teď porovnáš ten prvek 2,5 s jeho předchůdcem (tedy s prvkem 8). 2,5 < 8 takže prvky přehodíš, viz další obrázek


Pak zas porovnáš 2,5 s předchůdcem (tedy s prvkem 4). 2,5 < 4 takže je zas přehodíš, viz další obrázek

Pak zas porovnáš 2,5 s jeho předchůdcem (tedy s prvkem 2). 2,5 > 2 takže už nic nepřehazuješ a máš hotovo.


Co je dobrý si uvědomit?
Jak vidíš to pole nebude seřazený podle velikosti prvků. To sem tak zvolil jenom na začátku aby to pěkně vypadalo. Stejně tak neplatí, že levý poduzel je vždycky menší než pravý poduzel (Zkus si do toho posledního stromu vložit třeba uzel s hodnotou 3 a všimni si kam ti spadla 4ka). Jediný co máš tady jistý je, že rodičovský uzel bude vždycky větší (nebo roven) než oba jeho poduzly. Jak v takovýhle struktuře vyhledávat? Nad tím sem si chvíli lámal hlavu a pak mi došlo, že nijak :) Tohle neni binární vyhledávací strom. Dá se sem jenom vkládat novej prvek, odebrat nejmenší nebo zjistit hodnotu nejmenšího přesně tak jak to je v tom návodu...