Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Очередь с приоритетом

Очередь с приоритетом - структура данных, представляющая собой очередь, элементы которой распределены по приоритету.

Листинг Delphi

const HeapLength = 10000;
type HeapData = integer;
     Heap = object
       public
         A : array[1..HeapLength] of HeapData;
         size : integer;
       public
         constructor Create;
         function Parent(i : integer) : integer;
         function Left(i : integer) : integer;
         function Right(i : integer) : integer;
         procedure Heapify(i : integer);
         procedure Build(N : integer);
         procedure Sort(N : integer);
     end;

implementation
  
constructor Heap.Create;
  begin
    size := 0;
  end;

  function Heap.Parent(i : integer) : integer;
  begin
    Result := i shr 1;
  end;

  function Heap.Left(i : integer) : integer;
  begin
    Result := i shl 1;
  end;

  function Heap.Right(i : integer) : integer;
  begin
    Result := (i shl 1)+1;
  end;

  procedure Heap.Heapify(i : integer);
    var l, r, largest : integer;
        t : HeapData;
  begin
    l := Left(i);
    r := Right(i);
    if (L <= size) and (A[l] > A[i])
      then largest := l
      else largest := i;
    if (r <= size) and (A[r] > A[largest])
      then  largest := r;
    if largest <> i
      then begin
             t := A[i];
             A[i] := A[largest];
             A[largest] := t;
             Heapify(largest);
           end;
  end;

  procedure Heap.Build(N : integer);
    var i : integer;
  begin
    size := N;
    for i := N shr 1 downto 1
      do Heapify(i);
  end;

  procedure Heap.Sort(N : integer);
    var i : integer;
        t : HeapData;
  begin
    Build(N);
    for i := N downto 2
      do begin
           t := A[1];
           A[1] := A[i];
           A[i] := t;
           dec(size);
           Heapify(1);
         end;
  end;

09.12.2007, 18:01