Prioriteettijonot ja keko

  1. Johdanto ja määritelmiä
  2. Keon esittäminen taulukkona
  3. Minimikeko vs. maksimikeko
  4. Alkion lisääminen
  5. Suurimman alkion poistaminen
  6. Kekoehdon ylläpito (maksimikeko)
  7. Keon rakentaminen
  8. Kekojärjestäminen
  9. Keon korkeus

5. Suurimman alkion poistaminen

Yleisesti:

1. Vaihda juuren paikalle keon viimeinen alkio

2. Poista viimeinen alkio keosta

3. Valuta juureksi siirretty alkio oikealle paikalleen keossa (ks. MAX-HEAPIFY)

Pienimmän alkion poistaminen minimikeosta (MinHeap)

Laitetaan keon juuri talteen ja korvataan se keon viimeisellä alkiolla (joka poistetaan samalla keon lopusta). Tämän jälkeen korjataan kekoehto 'valuttamalla' juuressa olevaa alkiota oikealle paikalle keossa vaihtamalla se aina pienemmän lapsensa kanssa. Näin jatketaan, kunnes kekoehto on jälleen voimassa. Lopuksi poistoalgoritmi palauttaa talteen laitetun alkuperäisen juuren.

Suurimman alkion poistaminen maksimikeosta (MaxHeap)

Maksimikeossa (MaxHeap) toimitaan vastaavalla tavalla kuin edellä, mutta nyt alaspäin siirrettävä alkio vaihdetaan aina suuremman lapsen kanssa. Ks. MAX-HEAPIFY-algoritmi.


Edellinen luku: Alkion lisääminen Seuraava luku: Kekoehdon ylläpito (maksimikeko)

This document was last updated 03.11.2011. Please send your comments to Mikko Laakso and Ari Korhonen.