Stránka 1 z 1

[Java]Jak donutit PriorityQue,přesypat se při změně prvku.

Odeslat příspěvekNapsal: 5. 11. 2006 14:01
od Vebloud
Ahoj,

používám, PriorityQue kolekci a vždycky když odeberu prvek ze špice, tak se podle určitých kritérii mění hodnoty objektů ve frontě a to zrovna ty podle kterých se řadí. Problém je v tom, že ta fronta se nepřehází a to celkem pochopitelně, protože neví, že se ty prvky změnili. Potřeboval bych jí něják donutit tomu, aby se bud na povel zvenku přesypala, nebo jestli umí reagovat na nějáký onchange, tak na tom. Uť Googlím jak Googlím nic nemůžu najít.

Předem dík za odpověď.

Odeslat příspěvekNapsal: 5. 11. 2006 14:51
od Benjamin
Otazka je, jestli je rozumne pouzivat prioritni frontu, kdyz z ni potrebujes vzdycky odebrat jenom jeden prvek a pak ji celou presypat. Nebylo by lepsi mit obycejne pole a vzdycky v nem najit nejmensi prvek?

Odeslat příspěvekNapsal: 5. 11. 2006 14:55
od Vebloud
Nepřesypu jí celou. Změním několik málo prvků, bude jich tam něco kolem 10 000 a změním 0 - 4 prvky, přibližně. Pokud to dám do pole, tak se dostávám na nechutnou složitost, přesípání Heap Based PriorityQueue je určitě rychlejší, než vyhledávání nejmenšího prvku v neseřazeným poli.

Havně mi to poradili ve škole jako zeefektivňující věc, takže tak.

Odeslat příspěvekNapsal: 5. 11. 2006 15:00
od Benjamin
Pak je jeste otazka, jestli ta kolekce umoznuje odebrat i jiny nez nejmensi prvek. Pokud ano, tak ty zmenene proste odeber a vrat, pokud ne, budes muset najit neco jineho.

Odeslat příspěvekNapsal: 5. 11. 2006 15:04
od Vebloud
Benjamin píše:Tak ty zmenene proste odeber a vrat, pokud ne, budes muset najit neco jineho.


Umí to a už mě taky napadlo, ale připadá mi to nějáký nehezký, ale asi mi nic jinýho nezbyde.

Odeslat příspěvekNapsal: 6. 11. 2006 14:24
od duracellko
Neviem, ci v Jave existuje nejaka implementacia Red-Black Tree alebo nejakeho ineho binarneho vyhladavacieho stromu. Celkom urcite exituje, ale prakticky som v Jave nerobil.

Takze mozes pouzit tento Binary Search Tree.. zlozitost vkladania a vyberania je rovnaka ako v halde.. O(log n).. a mozes vyberat lubovolny prvok.

Odeslat příspěvekNapsal: 7. 11. 2006 15:58
od Vebloud
Tady nejde o to, že bych se k tém prvkům neměl jak dostat, jsou tam tam uzly grafu ke kterejm mám přístup i jinudy než přes tu PriorytiQueue.

Odeslat příspěvekNapsal: 7. 11. 2006 16:05
od Ageran
Řešit úkol na MEP na Živě mě nenapadlo :-) Příště to také zkusím...

Odeslat příspěvekNapsal: 7. 11. 2006 16:39
od Vebloud
Není to na MEP, ale PTE a co je MEP nemám ponětí. A ještě s jedním detailem, tohle už je navíc, protože do úkolu si musím tu haldu implementovat sám přes pole a nepoužívat už hotvou z Javy.

Odeslat příspěvekNapsal: 8. 11. 2006 13:30
od Ageran
MEP jsou Metodiky programování a je to úplně to samé, co Programovací techniky, jenže v dobýhajícím studiu :-)

Odeslat příspěvekNapsal: 11. 11. 2006 15:27
od xtonda (novy)
duracellko píše:Neviem, ci v Jave existuje nejaka implementacia Red-Black Tree alebo nejakeho ineho binarneho vyhladavacieho stromu. Celkom urcite exituje, ale prakticky som v Jave nerobil.

Takze mozes pouzit tento Binary Search Tree.. zlozitost vkladania a vyberania je rovnaka ako v halde.. O(log n).. a mozes vyberat lubovolny prvok.


Na červeno černém stromu je v Javě postavena TreeMap a TreeSet