Ako rozumiem, binary heap nepodporuje odstránenie náhodných prvkov. Čo keď potrebujem odstrániť náhodné prvky z a binary heap?
Je zrejmé, že môžem odstrániť prvok a znova usporiadať celú hromadu O(N), Môžem robiť lepšie?
odpovede:
22 pre odpoveď č. 1Áno a nie.
Problém je v tom binárna halda nepodporuje vyhľadávanie pre svojvoľný prvok. Nájdenie je samo o sebe O(n).
Ak však máte na prvok ukazovateľ (a nielen jeho hodnotu) - môžete zameniť prvok za ten pravý list, tento list odstrániť a potom znova heapifikovať príslušnú podskupinu (preosievaním novo umiestneného prvku podľa potreby). Výsledkom je O(logn) odstránenie, vyžaduje sa však ukazovateľ na skutočný hľadaný prvok.
8 pre odpoveď č. 2
Amit má pravdu vo svojej odpovedi, ale tu je ešte jedna nuansa:
pozíciu odstránenej položky (kam ste ju umiestnili)môže sa požadovať, aby sa prebublali listy (v porovnaní s rodičmi a pohybovali sa nahor, kým rodič nebude väčší ako vy). Niekedy je potrebné bubliny nadol (porovnajte s deťmi a choďte dolu, kým všetky deti nie sú menšie ako vy). Všetko záleží na prípade.
3 pre odpoveď № 3
Závisí od toho, čo sa myslí „náhodným prvkom“. Ak to znamená, že halda obsahuje prvky [e1, e2, ..., eN] a niekto chce odstrániť nejaké ei (1 <= i <= N), potom je to možné.
Ak používate implementáciu binárnej haldy z nejakej knižnice, je možné, že vám neposkytuje požadované rozhranie API. V takom prípade by ste mali hľadať inú knižnicu, ktorá ju má.
Keby ste to implementovali sami, potrebovali by ste ďalšie dve hovory:
Procedúra deleteAtIndex (halda, i), ktorá sa vymažeuzol v indexe i umiestnením posledného prvku do poľa haldy na i, dekrementáciou počet prvkov a nakoniec zamiešanie nadol / nahor nový prvok, ktorý udržuje invariantnú haldu. Najviac Bežným použitím tohto postupu je „pop“ halda volaním deleteAtIndex (halda, 1) - za predpokladu indexovania 1 pôvodu. Táto operácia spustí O (log n) (na dokončenie si však všimnem, že najvyššia hranica môže byť vylepšené až na O (log (log n)) v závislosti od niektorých predpokladov týkajúcich sa kľúčov vašich prvkov).
Procedúra deleteElement (halda, e), ktorá sa vymažeprvok e (váš ľubovoľný prvok). Váš algoritmus haldy by udržoval pole ElementIndex tak, aby sa vrátilo ElementIndex [e] aktuálny index prvku e: volanie deleteAtIndex (halda, ElementIndex [e]) potom urobí, čo chcete. Spustí sa tiež v O (log n), pretože prístup k poliam je konštantný.
Pretože binárne haldy sa často používajú v algoritmochktoré iba zobrazujú najvyššie (alebo najnižšie) Prioritný prvok (namiesto odstránenia ľubovoľných prvkov) si predstavujem, že niektoré knižnice môžu v API deleteAtIndex minúť, aby ušetrili miesto (vyššie uvedené vyššie uvedené pole ElementIndex).