Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

        STUDIA        

Implementacja kolejki priorytetowej w c++



  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
3 odpowiedzi w tym temacie

#1 Gość_Karis126_*

Gość_Karis126_*
  • Gość

Napisano 11.03.2017 - 19:21

Proszę o zaimplementowanie kolejki priorytetowej opartej na kopcu binarnym w c++.


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 901 postów
414
Instruktor II
  • Płeć:Mężczyzna

Napisano 12.03.2017 - 19:19

Czytałeś rozdział 7. Cormena Wprowadzenie do algorytmów ?

Tam masz przydatne funkcje

 

Pewnie nie możesz korzystać z STL

 

Kopiec binarny możesz zrealizować na tablicy albo na drzewie

Jeśli chodzi o reprezentację tablicową to potrzebujesz odpowiedników takich funkcji jak malloc ,realloc,free

Funkcję malloc zastąpisz przez new , funkcję free zastąpisz przez delete natomiast nie mam pomysłu jak zastąpić realloc

 

Reprezentacja drzewiasta będzie nieco wolniejsza

 

 

Reprezentacja tablicowa kopca

unit uheap;
interface
const maxA=1000;
type TElem=integer;
     TArray=array[1..maxA]of TElem;
     THeap=record
             data:TArray;
             arraylength,heapsize:integer;
           end;

function Parent(i:integer):integer;
function Left(i:integer):integer;
function Right(i:integer):integer;
procedure heapify(var A:THeap;i:integer);
procedure buildHeap(var A:THeap);
procedure heapSort(var A:THeap);
function heapExtractMax(var A:THeap;var error:integer):TElem;
procedure heapInsert(var A:THeap;key:TElem);

implementation

procedure swap(var x:TElem;var y:TElem);
var temp:TElem;
begin
 temp:=x;
 x:=y;
 y:=temp;
end;

function Parent(i:integer):integer;
begin
  Parent:=i div 2;
end;

function Left(i:integer):integer;
begin
  Left:=2*i;
end;

function Right(i:integer):integer;
begin
  Right:=2*i+1;
end;

procedure heapify(var A:THeap;i:integer);
var l,r,largest:integer;
begin
  l:=Left(i);
  r:=Right(i);
  if((l<=A.heapsize)and(A.data[l]>A.data[i]))
     then largest:=l
     else largest:=i;
  if((r<=A.heapsize)and(A.data[r]>A.data[largest]))
     then largest:=r;
  if (largest<>i) then
  begin
    swap(A.data[i],A.data[largest]);
    heapify(A,largest);
  end;
end;

procedure buildHeap(var A:THeap);
var i:integer;
begin
  A.heapsize:=A.arraylength;
  for i:=A.arraylength div 2 downto 1
    do heapify(A,i);
end;

procedure heapSort(var A:THeap);
var i:integer;
begin
  buildHeap(A);
  for i:=A.arraylength downto 2
    do begin
         swap(A.data[1],A.data[i]);
         A.heapsize:=A.heapsize-1;
         heapify(A,1);
       end;
end;

function heapExtractMax(var A:THeap;var error:integer):TElem;
var max:TElem;
begin
  error:=0;
  if A.heapsize<1 then
     error:=-1
  else
  begin
    max:=A.data[1];
    A.data[1]:=A.data[A.heapsize];
    A.heapsize:=A.heapsize-1;
    heapify(A,1);
    heapExtractMax:=max;
  end;
end;

procedure heapInsert(var A:THeap;key:TElem);
var i:integer;
begin
  A.heapsize:=A.heapsize+1;
  i:=A.heapsize;
  while((i>1)and(A.data[Parent(i)]<key))
    do begin
         A.data[i]:=A.data[Parent(i)];
         i:=Parent(i);
       end;
  A.data[i]:=key;
end;

begin

end.

Użytkownik Mariusz M edytował ten post 15.04.2017 - 13:28

  • 0

#3 kamil431

kamil431

    Ułamek

  • Jr Użytkownik
  • 5 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 21.04.2017 - 09:44

trochę trudne to są obliczenia


Użytkownik Jarekzulus edytował ten post 21.04.2017 - 11:50
spam

  • 0

#4 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 901 postów
414
Instruktor II
  • Płeć:Mężczyzna

Napisano 24.04.2017 - 20:15

To co tutaj mamy to tablicowa reprezentacja kopca oparta na pseudokodach Cormena i reszty

zapisana jako moduł w Pascalu

 

Zabrałby się ktoś za kopiec na drzewie

Nie jest to drzewo binarne bo z jednego węzła mamy dostęp do trzech węzłów , tzw ojca i tzw dwóch synów


  • 0