Куча (структура данных).

Имеется список целых чисел 5, 1, 7, 3, 9, 2, 8. Построим два дерева, в которых каждому узлу соответствует одно из значений этого списка, причем первое дерево будет организованно нисходящей иерархией, а второе – восходящей.

Два получившихся дерева полностью удовлетворяют свойству кучи: если Nявляется узлом-предком относительно M, а M соответственно узлом-потомком узла N, то для max-кучи всегда выполняется неравенство NM, а для min-кучи NM.

Когда корневой элемент кучи имеет наибольшее из возможных значений, то ее называют max-кучей, а когда наименьшее – min-кучей.

Данные, представленные такой структурой, удобны в обработке; некоторые операции с ними весьма не ресурсоемки, например, удаление минимального (для min-кучи) или максимального (для max-кучи) элемента, добавление нового элемента и др.

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

Пусть известно, с каким из видов дерева (min- или max-кучей) имеем дело. Тогда определить максимальный элемент max-кучи, и минимальный элемент min-кучи не составит труда, поскольку в обоих случаях это элемент под одним и тем же номером, а именно первый элемент массива. Составим программу на C++ для решения данной задачи.

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
const int N=7;
int i, j;
string T;
int s;
int min_heap[N]={1, 2, 3, 5, 7, 8, 9};
int max_heap[N]={9, 8, 7, 5, 3, 2, 1};

void Min()
{ cout<<"Корень min-кучи: "<<min_heap[0]; }
void Max()
{ cout<<"Корень max-кучи: "<<max_heap[0]; }
//главная функция
void main ()
{
setlocale(LC_ALL, "Rus");
cout<<"min-heap или max-heap? > "; cin>>T;
if (T=="min-heap") Min();
else if (T=="max-heap") Max();
else cout<<"Ошибка!";
system("pause>>void");
}

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

Рейтинг
( Пока оценок нет )
Загрузка ...