Void init_h(Heap *hp) {
init(&hp->v);
}
Функция получения максимального элемента Heap_Maximum также тривиальна, т.к. максимальный элемент всегда находится в начале массива:
Int Heap_Maximum(Heap *hp, double *z) {
if(hp->v.sz == 0) return 0; // если пирамида пуста
*z = hp->v.elem[0]; return 1;
}
Практический интерес представляют еще две операции над пирамидой:
включение в пирамиду нового элемента Max_Heap_Insert и
извлечение максимального элемента (удаление корня) Heap_Extract_Max.
Вопрос №78. Алгоритм включения в пирамиду нового элемента.
При построении алгоритмов реализации этих операций необходимо учитывать, что основное свойство пирамиды в результате их применения не должно нарушиться.
Разработаем алгоритм выполнения операции Max_Heap_Insert.
Первым шагом этого алгоритма будет включение нового элемента с помощью операции push_back для вектора, т.е. новый элемент помещается в конец массива. Рассмотрим пример:
К
ак
следует из рисунка, мы получили «слегка
испорченную» пирамиду, один элемент
которой стоит не «на месте». Очевидный
алгоритм «исправления» пирамиды
заключается в «подъеме» «неправильного
элемента» вверх по дереву путем его
сравнения и обмена местами (при
необходимости) с предком.
Следующие рисунки демонстрируют алгоритм «подъема» и запись этого алгоритма на языке С - текст функции Max_Heap_Insert:
Void Max_Heap_Insert(Heap *hp, double X){
hp->v.elem[(hp->v.sz)++] = x; // помещаем в конец массива
int i;
for(i = hp->v.sz-1; i > 0; i = (i-1)/2) { // «подъем»
if(hp->v.elem[(i-1)/2] > hp->v.elem[i]) return;
swapv(&hp->v, i, (i-1)/2); // обмен с предком
}
}
Вопрос №79. Алгоритм извлечения из пирамиды максимального элемента (удаление корня).
Разработаем алгоритм выполнения операции Heap_Extract_Max.
Рассмотрим пирамиду:
На первом шаге для удалению корня выполним две операции: переместим последний элемент в корень, а затем уменьшим на 1 счетчик количества элементов (т.е. переменную sz - размер вектора).
В результате также получим «слегка испорченную» пирамиду, один элемент которой (корень) стоит не «на месте». Очевидный алгоритм «исправления» пирамиды заключается в «спуске» «неправильного элемента» вниз по дереву путем его сравнения и обмена местами (при необходимости) с потомками.
Следующие рисунки демонстрируют алгоритм «спуска»:
Ниже приведён текст вспомогательной функции Max_Heapify, которая реализует алгоритм спуска «неправильного» элемента пирамиды с индексом i при условии, что левое и правое поддерево узла i обладают основным свойством пирамиды.
Void Max_Heapify(Heap *hp, int I) {
Int l, r, largest;
l = i*2+1; r = l+1; // индексы потомков слева и справа
if ((l < hp->v.sz) && (hp->v.elem[l] > hp->v.elem[i]))
largest = l;
else largest = i;
if ((r < hp->v.sz) && (hp->v.elem[r] > hp->v.elem[largest]))
largest = r;
if (largest != i) { // если один из потомков больше узла i
swapv(&hp->v, i, largest); // меняем местами
Max_Heapify(hp, largest); // рекурсивный вызов
}
}
С использованием функции Max_Heapify текст функции удаления вершины пирамиды Heap_Extract_Max будет выглядеть так: