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

Применим пирамиду для реализации структуры данных, состоящей из элементов и функций включения и извлечения элементов. С помощью функции извлечения читается наименьший из включенных элементов. Эта структура данных называется очередью с приоритетами.

Реализуем ее с помощью массива x[1],..., x [ n ], обладающего свойством пирамидальности в части 1:n . В начальный момент времени массив пуст, т.е. n=0 . Чтобы вставить новый элемент, мы увеличиваем n на 1 , добавляем новый элемент в массив, а затем расширяем свойство пирамидальности с помощью функции SiftUp(n) . В результате получаем пирамиду, наименьший элемент которой равен x[1] . Функция извлечения элемента будет читать элемент x[1], а затем, после перестановки последнего элемента x[n] на место x[1] , установит n=n-1 и вызовет функцию SiftDown(n) . Если очередь с приоритетами содержит не более 100 элементов, то для ее реализации можно предложить следующие данные и функции:

int n=0;

int x[101];

void swap(int *a, int *b)

{

int temp=*a;

*a=*b;

*b=temp;

}

void SiftUp(int n)

{

int i = n , p ;

while ( i >1) //пока не достигнут корень

{

p = i /2; //индекс сдвига

if ( x [ p ]<= x [ i ]) break ; //выход из цикла

swap(&x[p],&x[i]); // если x[p] > x[i]

i = p ; //то движение наверх

}

}

void SiftDown(int n)

{

int i=1,c;

while (( c =2* i )<= n ) //с – левый сын узла

{

if (( c +1)<= n ) //с+1 – правый сын узла

if ( x [ c +1]< x [ c ])

c = c +1; //наименьший сын

if(x[i]<=x[c]) break; // выход из цикла

swap (& x [ c ],& x [ i ]); //движение вниз

i=c;

}

}

int Insert(int n) // возвращает 0 при переполнении

{

if(n+1<100)

{

n++;

x[n]=t;

SiftUp(n);

return 1;

}

else return 0;

}

int ExtractMin(int *err) // возвращает наименьший

{

int t;

if(n<1)

{

*err=1; // ошибка

return 0;

}

t=x[1];

x[1]=x[n];

n--;

SiftDown(n);

* err =0;

return t ;

}