Napisalem taka kolejke na kopcu, mam dwa pytania:
- Jak pozbyc sie zmiennej globalnej? (tu za bardzo nie mozna przekazywac tego przy wywolywaniach)
- czy tak ma dzialac kolejka i czy dobrze dziala?
#include <stdio.h>
#include <time.h>
#include <limits.h>
#define N 10
//Kolejka priorytetowa na kopcu
int n=-1;
int parent(int i){return i/2;};
int left(int i){if(i==0)return 1; else return 2*i;};
int right(int i){if(i==0)return 2; else return 2*i+1;};
void heapify(int t[], int i);
//void build_heap(int t[]);
//void heapsort(int t[]);
int maximum(int t[]){if (n>=0) return t[0]; else printf("BRAK"); return 0;};
int extract_max(int t[]);
void increase_key(int t[], int i, int key);
void insert(int t[], int key);
int main(){
srand(time(0));
int t[N];
//int i=0;
/*for (i=0;i<N;++i)
t[i]=rand()%123;
for (i=0;i<N;++i)
printf("%d\t", t[i]);
//heapsort(t);
printf("\n\n\n");
for (i=0; i<N;++i)
printf("%d\t", t[i]);*/
int k;
printf("1-dodaj element, 2-zwroc max(najwiekszy klucz), 3-zwroc max i go usun, 4-zmien klucz, 0 - koniec\n");
scanf("%d", &k);
while (k){
if (k==1){
printf("podaj element(klucz)\n");
int e;
scanf("%d", &e);
insert(t,e);
}
else if (k==2){
printf("%d\n", maximum(t));
}
else if (k==3){
printf("%d\n", extract_max(t));
}
else if (k==4){
int i, w;
printf("podaj ktory element zaaktualizaowac\n");
scanf("%d", &i);
printf("podaj nowa wartosc\n");
scanf("%d", &w);
increase_key(t,i,w);
}
else
break;
printf("1-dodaj element, 2-zwroc max(najwiekszy klucz), 3-zwroc max i go usun, 4-zmien klucz, 0 - koniec\n");
scanf("%d", &k);
if (k!=1 && k!=2 && k!=3 && k!=4)
break;
}
printf("KONIEC\n");
return 0;
}
void heapify(int t[], int i){
int largest;
int l = left(i);
int r = right(i);
if (l < n && t[l] > t[i])
largest = l;
else
largest = i;
if (r < n && t[r] > t[largest])
largest = r;
if (largest != i){
int x;
x=t[i];
t[i]=t[largest];
t[largest]=x;
heapify(t, largest);
}
}
////////////////////////////////////////////////////////////////////////
/*void build_heap(int t[]){
int i;
for (i=N/2; i>=0; --i) //trafia w rodzicow
heapify(t,i,N);
}*/
////////////////////////////////////////////////////////////////////////
/*void heapsort(int t[]){
build_heap(t);
int i;
int n=N;
for (i=N-1; i>=1; --i){ //pamietaj zakres tablicy
int x=t[0];
t[0]=t[i];
t[i]=x;
--n;
heapify(t,0,n);
}
}*/
//////////////////////////////////////////////////////////////////////////
int extract_max(int t[]){
if (n<0){
printf("KURDE BLAD!!! Kopiec pusty\n");
return 0;
}
int max=t[0];
t[0]=t[n];
--n;
heapify(t,0);
return max;
}
//////////////////////////////////////////////////////////////////////////
void increase_key(int t[], int i, int key){
if (i<=n){
if (key<t[i])
printf("nowy klucz jest mniejszy niz aktualny!\n");
t[i]=key;
while (i > 0 && t[parent(i)] < t[i]){
int x = t[i];
t[i]=t[parent(i)];
t[parent(i)]=x;
i=parent(i);
}
}
else
printf("BLAD\n");
}
///////////////////////////////////////////////////////////////////////////
void insert(int t[], int key){
++n;
if (n<N){
t[n]=INT_MIN;
increase_key(t,n,key);
}
else
printf("przepelnienie!\n");
}