|
Titlul: k-lea minim Scris de: Nicolae Titus din Mai 27, 2009, 00:39:07 Salut,
exista o structura asemanatoare unui heap dar in care sa se poata sterge/modifica al k-lea minim? multumesc! Titlul: Răspuns: k-lea minim Scris de: Stefan Istrate din Mai 27, 2009, 08:13:19 Iti trebuie sa afli rapid doar al k-lea minim sau faci mai multe query-uri de forma asta?
Titlul: Răspuns: k-lea minim Scris de: Mircea Dima din Mai 27, 2009, 11:13:04 Poti folosi un arbore binar de cautare echilibrat (avl, treap, splay tree). In fiecare nod mentii
o variabila ce iti spune cate noduri sunt in subarbore. Folosind aceasta informatie poti raspunde in O(logn) la un query pt al k-lea minim. Daca vrei neaparat heap cred ca merge pe Fibonnaci Heaps... Titlul: Răspuns: k-lea minim Scris de: Andrei Grigorean din Mai 27, 2009, 11:25:29 K este constant?
Daca da, nu ai nevoie de un BST, poti sa iti mentii un max heap de marime K pentru cele mai mici elemente si un min heap pentru elementele mai mari decat a K-a valoare. Titlul: Răspuns: k-lea minim Scris de: Paul-Dan Baltescu din Mai 27, 2009, 11:32:13 Poti tine un trie cu numerele reprezentate pe biti. Ce nu suporta aceasta structura sunt intrebari: care este al K-lea minim pe un interval (x,y), dar pentru tot sirul merge.
Titlul: Răspuns: k-lea minim Scris de: Nicolae Titus din Mai 27, 2009, 15:52:12 Cautam o solutie pentru mai multe query-uri unde k e variabil. Interesanta ideea cu 2 heapuri pentru k constant.
Trie-ul desi cred ca merge mai incet in O(log(nr de biti)) pare mai usor de implementat. Pe arborele binar de cautare echilibrat se pot face query-uri pe intervale? Multumesc! Titlul: Răspuns: k-lea minim Scris de: Marius Stroe din Mai 27, 2009, 18:01:34 Cautam o solutie pentru mai multe query-uri unde k e variabil. Dacă K e variabil atunci poţi face cu Treapuri (http://www.infoarena.ro/treapuri). :) Pe arborele binar de cautare echilibrat se pot face query-uri pe intervale? Se poate face, dar nu sunt sigur de complexitate. Însă, prin analogie cu arborii de intervale, intuitiv, se păstrează O(log(N)) pe query. Titlul: Răspuns: k-lea minim Scris de: Andrei Grigorean din Mai 27, 2009, 18:27:55 Trieurile ocupa foarte multa memorie, si merg in 32 * O(N), ceea ce de multe ori e mai prost decat O(N log N). Pe de alta parte, sunt mai usor de imlementat :).
|