|
1. Prvo se uzimaju redom prvi elementi svake od lista i ubacuju u heap. Kad se ubaci i+1 čvor u heap, gubi se svojstvo heapa pa se on zamijeni sa svojim roditeljem, sa roditeljem svog roditelja, itd. dok se ponovno ne ostvari svojstvo heapa. Na kraju se dobije heap od n čvorova.
2. Vrati se oznaka korijena. Izbacimo zadnji čvor na najvišem nivou, a oznaku tog čvora upišemo u korijen. Time smo možda narušili svojstvo heapa pa se zamijeni oznaka korijena i oznaka njegovog manjeg djeteta, itd. dok se opet ne ostvari svojstvo heapa.
3. Uzme se prvi sljedeći element one liste čiju smo vrijednost vratili (ako takav postoji - prije ili kasnije ćemo isprazniti listu), tj. čija se vrijednost našla u korijenu u prethodnom koraku i stavimo ga u heap na zadnje mjesto u zadnjem nivou. Opet smo možda pokvarili svojstvo heapa pa se vrijednost tog čvora zamjenjuje sa vrijednošću njegovog roditelja, roditelja njegovog roditelja, itd. dok se ne ostvari svojstvo heapa.
4. Ponavljaju se koraci 2. i 3. dok se heap ne isprazni.
1. Prvo se uzimaju redom prvi elementi svake od lista i ubacuju u heap. Kad se ubaci i+1 čvor u heap, gubi se svojstvo heapa pa se on zamijeni sa svojim roditeljem, sa roditeljem svog roditelja, itd. dok se ponovno ne ostvari svojstvo heapa. Na kraju se dobije heap od n čvorova.
2. Vrati se oznaka korijena. Izbacimo zadnji čvor na najvišem nivou, a oznaku tog čvora upišemo u korijen. Time smo možda narušili svojstvo heapa pa se zamijeni oznaka korijena i oznaka njegovog manjeg djeteta, itd. dok se opet ne ostvari svojstvo heapa.
3. Uzme se prvi sljedeći element one liste čiju smo vrijednost vratili (ako takav postoji - prije ili kasnije ćemo isprazniti listu), tj. čija se vrijednost našla u korijenu u prethodnom koraku i stavimo ga u heap na zadnje mjesto u zadnjem nivou. Opet smo možda pokvarili svojstvo heapa pa se vrijednost tog čvora zamjenjuje sa vrijednošću njegovog roditelja, roditelja njegovog roditelja, itd. dok se ne ostvari svojstvo heapa.
4. Ponavljaju se koraci 2. i 3. dok se heap ne isprazni.
|
