бинарная куча

← →
sat © (2007-04-24 16:53) [0]

вообщем я написал процедуру и функцию для работы с бинарной кучей
(добавление жлемента в кучу и удаление минимального)

помогите отладить. где то в алгоритме допущена ошибка

procedure AddHeap (x , count : integer); //add to heap element var i : integer; begin inc(count); i := count; heap[0] := x; while (x < Heap[i div 2])do begin Heap[i]:=Heap[i div 2]; i:=i div 2 end; Heap[i] := x ; end; function deletemin(count:integer):integer; var i,child:integer; last_el:integer; stop:boolean; begin deletemin:=Heap[1]; last_el:=Heap[count]; dec(count); i:=1; stop:=False; while (2*i<=count) and (not stop) do begin child:=2*i; if child < count then if Heap[child+1] < Heap[child] then child:=child+1; if last_el > Heap[child] then begin Heap[i]:=Heap[child]; i:=child; end else stop:=True; end; {while} Heap[i]:=last_el; end;

← →
Сергей М. © (2007-04-24 16:55) [1]

> с бинарной кучей

Эт что еще за зверь ?)

← →
sat © (2007-04-24 16:57) [2]

есть такая структура используется для сортировки массива(очень быстрой n*log(n))...

просто где то допустил ошибку и не могу найти

← →
Сергей М. © (2007-04-24 17:00) [3]

Куча-то причем тут ? Это ж вроде бы термин из совсем другой оперы - вот что не понятно ..

← →
sat © (2007-04-24 17:01) [4]

нормальный термин binary heap

не надо путать с динамической памятью...

← →
MBo © (2007-04-24 17:05) [5]

heap[0] := x;

А нулевой элемент (вершину кучи) в мусорку?
Нужно записывать новый элемент последним и выполнять всплытие.

while (x < Heap[i div 2])do
это и дальнейшее не имеет смысла, однако уточню, что для куч в массиве с нумерацией с нуля отношение индексов будет не такое, как используется у тебя (твое соответствует нумерации с единицы)

Итак, разберись с организацией индексов элементов куч в zero-based массиве, напиши отдельные процедуры для всплытия и погружения, и используй их.

пример вставки нового элемента
if FCount = FSize then
Grow;
FA[FCount] := Value;// вставили последним
Inc(FCount);
FixUp(FCount - 1);//всплытие

извлечение минимума
Result := FA[0];
Dec(FCount);
FA[0] := FA[FCount]; //записали последний на место удаленного
FixDown(0) //погружение

> термин binary heap
>
> не надо путать с динамической памятью

А никто и не путает)

И дин.память с Windows heaps тоже никто не путает)

>Сергей М
Действительно есть такая структура данных - heap, куча, другое название - пирамида, используется в пирамидальной сортировке (HeapSort) и в очередях по приоритетам.
Конфликт имен, как с потоками thread/stream, блин ;)

бинарная куча Найти похожие ветки