Обработка кучи

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

HeapHead

¯ ¯ ¯ ¯

a_i+2

a_i

a_i+1  

Эффективное решение – связать свободные компоненты в список.

{Инициализация кучи}

procedure InitHeap(list:tList);

{Связать все компоненты от 1 до nMax}

begin

with list do

begin

for ptr:=1 to nMax do content[ptr].next:=succ(ptr);

content[nMax].next:=Æ; {Признак конца стека}

end;

end;

procedure GetHeap(var list:tList;NewPtr:tIndex);

{Взять указатель на свободную компоненту из кучи}

begin

with list do

begin

NewPtr:=HeapHead;

HeapHead:=content[HeapHead].next;

end;

end;

procedure PutHeap(var list:tList;Ptr:tIndex);

{Кладёт элемент в кучу}

begin

with list do

begin

content[Ptr].next:=HeapHead;

HeapHead:=Ptr;

end;

end;

Упражнение. Реализовать вставку и удаление из обработанного и двусвязного списка.

Дата добавления: 2014-01-05