Реализация очереди с приоритетами на базе пирамиды

Очередь с приоритетами также часто реализуют с помощью пирамиды. При этом извлечение элемента с максимальным приоритетом из очереди осуществляется аналогично тому, как это делалось во 2-й фазе алгоритма пирамидальной сортировки.

Вставка элемента в очередь происходит похожим образом – помещаем элемент в конец пирамиды (увеличив её размер на единицу) и обеспечиваем выполнение основного свойства пирамиды для этого элемента. Основное отличие состоит в том, что при этом мы сравнивать элемент с его родителем (а не сыном) и при необходимости поднимать, а не опускать. Пример вставки элемента показан на рис.4.9.

Иногда требуется, чтобы элементы с одинаковым приоритетом выходили из очереди в том же порядке, в каком они и пришли. Для этого можно использовать разные способы, например, расширить приоритеты элементов очереди до двух частей – собственно приоритета и некоего порядкового номера, который будет увеличиваться на единицу для каждого нового элемента, помещаемого в очередь.

0	1	2	3	4	5	6	7
9	7	5	6	2	4	1	3

 

0	1	2	3	4	5	6	7	8
9	7	5	6	2	4	1	3	8

 

0	1	2	3	4	5	6	7	8
9	7	5	8	2	4	1	3	6

 

0	1	2	3	4	5	6	7	8
9	8	5	7	2	4	1	3	6

Рис 4.9. Вставка элемента в очередь с приоритетами на базе пирамиды

Сортировка слиянием

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

Например, пусть заданы последовательности <2,5,8> и <3, 4>. Сначала сравним элементы 2 и 3, меньший из них 2 – он станет первым элементом результата, а у нас остаётся <5,8> и <3,4>. Теперь 3 меньше чем 5, 3 уходит в результат, у нас остаётся <5,8> и <4>. На следующем шаге 4 уходит, и вторая последовательность становится пустой. Для завершения слияния остаток первой последовательности уходит в результат. Более наглядно этот процесс показан на рисунке.

В случае, когда последовательности заданы в массивах, для текущего первого элемента последовательности можно просто использовать отдельную переменную – индекс. приведём пример реализации (a и b – исходные массивы, n и m – их длины, r – массив, куда помещается результат):

void merge(int a[], int n, int b[], int m, int r[])

{ int i=0, j=0, k=0;

while (i<n && j<m)

r[k++] = (a[i]<=b[j])? a[i++]: b[j++];

//добавим остаток первого массива

for(; i<n; i++)

r[k++] = a[i];

//добавим остаток второго массива

for(; j<m; j++)

r[k++] = b[j];

}

Теперь перейдём к алгоритму сортировки слиянием. Рекурсивная реализация данного алгоритма очень легка и проста для понимания. Чтобы отсортировать массив, мы разбиваем его на две примерно равные части, рекурсивно сортируем каждую из них, после чего сливаем отсортированные части и получаем результирующий отсортированный массив.

Большим недостатком данного алгоритма является необходимость выделения памяти под вспомогательный массив, куда помещаются результаты слияния двух половинок исходного массива.

Пример реализации:

void _mergeSort(int a[], int n, int r[])

{ бif (n<2) return;

//разбиваем на две части, рекурсивно сортируем левую и правую часть

int p = n/2;

_mergeSort(a,p,r);

_mergeSort(a+p,n-p,r);

//сливаем отсортированные части во вспомогательный массив b

merge(a,p,a+p,n-p,r);

//копируем отсортированные данные из b обратно в a

memcpy(a,r,n * sizeof(int));

}

void mergeSort(int a[], int n)

{

int *r = new int[n];

_mergeSort(a,n,r);

delete [] r;

}

Здесь основная работа выполняется в функции _mergeSort, рекурсивно вызывающей саму себя, тогда как в функции-оболочке mergeSort выделяется и освобождается память под вспомогательный массив.

Нерекурсивный вариант данной сортировки будет рассмотрен в главе, посвященной внешней сортировке.