Kaudze / Summaries, Notes / ID: 415303

Author: Artis Sproģis (19)

Evaluation:

Published: 27.12.2013.

Language: Latvian

Level: College/University

Literature: 5 units

References: Not used

Time period viewed: 2011 - 2015 years

Enlarge preview

Table of contents

Nr.	Chapter	Page.
1.	Kaudze (Heap sort)	4
1.1.	Pārskats	4
1.2.	Kas ir kaudze	4
1.3.	Kaudzes algoritms (mazākā elementa izmešana)	5
1.4.	Kārtošana ar kaudzi (Heap Sort)	7
1.5.	Kaudzes kārtošanas algoritms	7
1.6.	Kaudzes kārtošanas algoritma realizācija C++	9
1.7.	Piemērs	10
1.7.1.	Izveido kaudzi	10
1.7.2.	Kārto kaudzi	10
	Secinājumi	11
	Izmantotais izziņas avotu saraksts	12

Extract

1.4. Kārtošana ar kaudzi (Heap Sort)
Ja rindu ar prioritāti realizējam ar kaudzes palīdzību, tad nav nepieciešama papildus atmiņa, t.i. kaudzi var realizēt tajā pašā tabulā, kurā atrodas kārtojamie elementi. Indekss i tabulā nosaka robežu starp sakārtoto un nesakārtoto tabulas daļu. Kaudze ir realizēta nesakārtotajā daļā: intervālā A[i..n-1]. Kaudzes sakne (mazākais elements) atrodas labajā pusē pozīcijā A[n-1]. Līdz ar to kaudze dilst no kreisās puses, bet sakārtotā daļa, aizņemot kaudzes atbrīvoto vietu, pieaug no labās puses. Indekss i pavirzās pa labi un nosaka jauno robežu.
Algoritma ideja: samainām kaudzes sakni ar pašu kreisāko elementu nesakārtotajā daļā un veicam kaudzes "atjaunošanas darbus" ar procedūras Heapify palīdzību. Darbojoties ar kaudzi algoritmā Heapify ir jāatceras, ka atšķirībā no kaudzes standartrealizācijas tabulā (no kreisās uz labo), šoreiz kaudze ir apgriezta otrādi (no labās uz kreiso).
…

Author's comment

Work pack:

GREAT DEAL buying in a pack ➞ your savings −4,98 €

Work pack Nr. 1336184

Purchase a work pack of 3

Show work pack

Summaries, Notes

Technologies

Computers, Consumer Electronics