Keon korkeus on sen juuren korkeus. Voidaan
osoittaa, että n-alkioisen keon korkeus on ⌊lg n⌋
Esimerkki 2: Jos keossa on 10 alkiota; n = 10, niin keon korkeus on ⌊lg 10⌋ =
⌊3,32...⌋ = 3.
MAX-HEAPIFY:n kompleksisuus eli pahimmassa tapauksessa MAX-HEAPIFY-rutiinia kutsutaan kerran jokaisella keon tasolla.
Tasoja on h + 1 = ⌊lg n⌋ + 1 kappaletta.
Tästä seuraa suoraan, että algoritmin aikakompleksisuus T(n) = O(lg n).
Alkion lisäys- ja poisto-operaatioiden kompleksisuus
Koska alkion poisto-operaatio käyttää HEAPIFY-algoritmia, on poisto-operaation kompleksisuus myös O(lg n).
Tehtäviä: Analyysi
a) Analysoi yksittäisen alkion lisäyksen pahimman tapauksen aikakompleksisuus.
b) Päättele myös mikä on keon rakentamisen (lisätään kekoon N alkiota) aikakompleksisuus yksittäisten lisäysten avulla.
a) Mikä on kekojärjestämisen pahimman tapauksen aikavaatimus?
This document was last updated 03.11.2011. Please send your comments to Mikko Laakso and Ari Korhonen.