Отправляет email-рассылки с помощью сервиса Sendsay

Разбор классических алгоритмов и олимпиадных задач.

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 977 RSS
←   Июнь 2005   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
09.06.2005
12:12:18
13:22:33
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Открыта: 01-08-2004

Автор
ferrik

Статистика

977 подписчиков
0 за неделю
←   Все выпуски   →

Разбор классических алгоритмов и олимпиадных задач. Пирамидальная сортировка.


Информационный Канал Subscribe.Ru
 Здравствуйте.
В этот раз в статья много картинок, без них она не имеет смысла, так что их желательно загрузить.

Пирамидальная сортировка.
Дерево -- коллекция узлов, каждый из которых (кроме корневого) имеет родительский узел и какое-то количество дочерних узлов.
Узлы, которые не имеют дочерних узлов называют листьями.
Дерево называют бинарным, если все узлы содержат не более двух дочерних узлов.
Узлы бинарного дерева описываются так: 
type 
  PTreeNode=^TTreeNode 
  TTreeNode = record 
    ptParent, ptLChild, ptRChild :PTreeNode; 
    Data :integer; 
  end;

Бинарное дерево называется пирамидой, если:
1) Все листья расположены на двух последних уровнях.
2) Предпоследний уровень заполнен полностью, а в последнем все элементы максимально сдвинуты влево..
3) Дочерние узлы меньше родительских или равны им.

Разберём подробней 3 пункт. Но сначала надо определиться с тем, как хранить пирамиду. Использовать указатели в нашем случае не выгодно. Зная особенности пирамиды, правильнее хранить её в массиве.

Допустим, у нас есть массив из 15 элементов: 

array [0..14] of integer=(57, 71, 96, 32, 10, 85, 73, 83, 88, 98, 20, 45, 36, 89, 81);
На основе этого массива построим бинарное дерево, обладающее двумя первыми признаками пирамиды.

Чтобы начать преобразовывать это дерево в пирамиду надо рассмотреть алгоритм просачивания.

Допустим, дерево представляет из себя две пирамиды соединённые корневым узлом(см. рисунок 2). Будем применять алгоритм просачивания для [0] элемента. Сравним его с наибольшим дочерним элементом ([0] c [1]). Так как [0] элемент меньше то обменяем их (см. рис. 3). На следующем этапе все эти операции проведём для [1] элемента, и т. д. до тех пор пока 1 не встанет(просочиться) на своё место (рис. 4).

procedure HeapDown(_Ind, _MaxInd : integer); 
var 
  ChildInd, StartValue:integer; 
begin 
  StartValue:=a[_Ind]; 
  ChildInd:=(_Ind*2)+1; 
  while ChildInd <= _MaxInd do 
  begin 
    if (ChildInd + 1 <= _MaxInd) and (a[ChildInd] < a[ChildInd+1]) then 
      inc(ChildInd); 
    if StartValue >= a[ChildInd] then break; 
    a[_Ind]:=a[ChildInd]; 
    _Ind:=ChildInd; 
    ChildInd:=(_Ind * 2) + 1 
  end; 
  a[_Ind]:=StartValue; 
end;

Вернёмся к задаче. Для построения пирамиды необходимо, начиная с родительского узла самого правого дочернего узла просочить все элементы расположенные левее и не ниже. В нашем случае (рис.1) это элементы с 0-го по 6-ой. 

procedure GenerateHeap(_MaxInd:integer); 
var 
  i:integer; 
begin 
  for i:=(_MaxInd-1) div 2 downto 0 do 
    HeapDown(i,_MaxInd); 
end;
Самая интересная особенность пирамиды в том, что максимальный элемент всегда наверху (докажите). Но как её использовать. Надо поменят местами корневой и последний элементы и уменьшить кол-во элементов на 1. В нашем примере мы должны в 0-ую позицию поместить 81. Свойство пирамидальности скорее всего будет нарушено и для восстановления оного надо будет применить алгоритм просачивания для нового корневого элемента. И так до тех пор пока кол-во элементов в массиве больше 1.
while L>=1 do 
begin 
  t:=a[L];a[L]:=a[0];a[0]:=t; 
  Dec(L); 
  HeapDown(0, L); 
end;


Замеры, мс
Кол-во 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
Bubble 0.0025 0.0085 0.0323 0.1293 0.5214 2.0936 8.3018 32.793 130.88 532.87 2151.6 8685.4 47761
Shaker 0.0025 0.0080 0.0282 0.1092 0.4288 1.6955 6.7565 26.718 106.15 426.11 1716.6 6896.2 30936
Selection 0.0024 0.0070 0.0222 0.0772 0.2831 1.0826 4.1964 16.536 65.508 263.50 1054.2 4213.4 19436
Insertion 0.0012 0.0034 0.0114 0.0416 0.1588 0.6169 2.4413 9.7193 38.740 154.76 618.77 2474.2 13597
InsertionO 0.0013 0.0033 0.0099 0.0338 0.1238 0.4723 1.8481 7.3261 29.112 116.23 463.99 1855.5 11466
QuickSort 0.0027 0.0062 0.0137 0.0300 0.0650 0.1400 0.3000 0.6400 1.3600 2.9000 6.1400 13.000 28.100
QuickSortO 0.0016 0.0040 0.0092 0.0210 0.0468 0.1000 0.2250 0.4910 1.0600 2.2800 4.8700 10.410 23.270
HeapSort 0.0027 0.0061 0.0136 0.0305 0.0678 0.1493 0.3261 0.7000 1.5400 3.3800 7.4100 15.930 37.570

Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора 		Подписан адрес:
Код этой рассылки: comp.soft.prog.fprogram 		Отписаться
Вспомнить пароль
В избранное