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

4. Alkion lisääminen

Uuden alkion lisääminen kekoon:

1. Laita uusi alkio keon viimeiseksi alkioksi (tasot täyttyvät vasemmalta oikealle)

2. Nosta lisätty alkio keossa oikeaan kohtaan tekemällä vaihtoja isäsolmun kanssa kunnes kekoehto on jälleen voimassa

Keon rakentaminen lisäämällä alkiot yksi kerrallaan

Lisäys-operaatioilla keon rakentaminen on varsin suoraviivainen toiminto. Siinä vain lisätään yksitellen kukin alkio keon viimeiseksi alkioksi, ja tämän jälkeen nostetaan lisätty alkio keossa oikealle paikalle.

Tehtäviä: Lisäys

Lisää alkiot annetussa järjestyksessä yksitellen oheiseen kekoon.
Lisäyksessä vedä ja pudota alkiot annetussa järjestyksessä kekorakenteen tyhjiin solmuihin. Palauta kekoehto voimaan kunkin lisäyksen jälkeen. Huomaa, että tehtävässä alkioiden vedä ja pudota -toiminnallisuus vaihtaa lähtö- ja kohdesolmun alkiot keskenään.
Algorithm 1 MaxHeap-Insert(A, key)

heap-size[A] ← heap-size[A] + 1
i ← heap-size[A] - 1
while i > 0 and A[Parent(i)] < key
do A[i] ← A[Parent(i)]
i ← Parent(i)
A[i] ← key

Edellinen luku: Minimikeko vs. maksimikeko Seuraava luku: Suurimman alkion poistaminen

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