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

8. Kekojärjestäminen

Kekoa voidaan hyödyntää myös järjestämiseen. Maksimikeko rakennetaan ensin lineaarisessa ajassa toimivalla algoritmilla, jonka jälkeen siitä poistetaan yksitellen N kertaa suurin alkio. Poistettu alkio voidaan sijoittaa samaan tilaan poistossa juuri vapautuneeseen paikkaan. Koska alkiot poistetaan suurimmasta pienimpään (maksimikeko) ja poistettu alkio sijoitetaan aina taulukon lopusta vapautuneeseen paikkaan, saadaan alkiot järjestettyä pienimmästä suurimpaan.

Tehtäviä: a) Kekojärjestäminen

Oheista kekojärjestämisalgoritmista on suoritettu rivit 1 ja 2. Tehtävänä on suorittaa algoritmi loppuun (silmukka riveillä 3-6).

Voit vaihtaa kahden avaimen paikkaa keskenään vetämällä ja pudottamalla avaimen toisen päälle kummassa tahansa näkymässä (taulukko tai binääripuu). Aloita vaihtamalla keon viimeinen alkio sen suurimman alkion kanssa ja suorita sen jälkeen MaxHeapify-algoritmin edellyttämät vaihdot, joissa taulukko palautetaan keoksi.

Algorithm 5 HeapSort(A)

1: Build-Max-Heap(A)
2: heapsize ← heap-size[A]
3: while heapsize > 1 do
4: A[heapsize] ← Heap-Extract-Max (A)
5: heapsize ← heapsize - 1
6: end while

b) Onko kekojärjestäminen stabiili järjestämismenetelmä?



Edellinen luku: Keon rakentaminen Seuraava luku: Keon korkeus

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