k-lea minim

[•nicolaetitus12]

Salut,
exista o structura asemanatoare unui heap dar in care sa se poata sterge/modifica al k-lea minim?
multumesc!

[•stef2n]

Iti trebuie sa afli rapid doar al k-lea minim sau faci mai multe query-uri de forma asta?

[•blasterz]

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...

[•wefgef]

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.

[•pauldb]

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.

[•nicolaetitus12]

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!

[•Marius]

Cautam o solutie pentru mai multe query-uri unde k e variabil.

Dacă K e variabil atunci poţi face cu 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.

[•wefgef]

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 .