Пример результата просеивания

Дата добавления: 2014-02-04; просмотров: 881; Нарушение авторских прав

Просеивание

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах³⁾ последовательно задерживаются сначала крупные, а затем все более мелкие частицы.

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

a[1]
a[2]	a[3]
a[4]	a[5]	a[6]	a[7]
a[8]	a[9]	a[10]	a[11]	a[12]

Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].

При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:

for i:= (N div 2)downto 1 do begin j:= i; while j<=(N div 2) do begin k:= 2*j; if (k+1<=N) and (a[k]<a[k+1]) then k:= k+1; if a[k]>a[j] then begin x:= a[j]; a[j]:= a[k]; a[k]:= x; j:= k end else break endend;

Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).

Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):







	10 9
		9 10



11 4
4 11

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:


	12 5
		5 12


11 7
7 11

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1
	1 12
7 1


	8 1
		1 8



		6 1
				1 6

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

<== предыдущая лекция	\|	следующая лекция ==>
	\|	Символы и строки