| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

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

sat ©   (2007-04-24 16:53:00) 

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

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


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;



---

MBo   (2007-04-24 17:10:00) [1]

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

---

Сергей М.   (2007-04-24 17:06:00) [2]

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


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

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

---

MBo   (2007-04-24 17:05:00) [3]

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)  //погружение

---

sat   (2007-04-24 17:01:00) [4]

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

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

---

Сергей М.   (2007-04-24 17:00:00) [5]

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

---

sat   (2007-04-24 16:57:00) [6]

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

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

---

Сергей М.   (2007-04-24 16:55:00) [7]

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


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

---

Наверх