Proszę o zaimplementowanie kolejki priorytetowej opartej na kopcu binarnym w c++.
Implementacja kolejki priorytetowej w c++
#1 Gość_Karis126_*
Napisano 11.03.2017 - 19:21
Napisano 25.09.2011 - 17:55
#2
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
#3
Napisano 21.04.2017 - 09:44
trochę trudne to są obliczenia
Użytkownik Jarekzulus edytował ten post 21.04.2017 - 11:50
spam
#4
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