Куча в программировании. Основные принципы программирования: стек и куча. Просеивание и равенство элементов
Представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков .
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча , поскольку корень поддерева является максимумом из значений элементов поддерева.
В качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами .
Двоичную кучу удобно хранить в виде одномерного массива, причем
- левый потомок вершины с индексом i имеет индекс 2*i+1,
- правый потомок вершины с индексом i имеет индекс 2*i+2.
Корень дерева (кучи) – элемент с индексом 0.
Высота двоичной кучи равна высоте дерева, то есть
log 2 (N+1) ,
где N – количество элементов массива, – округление в большую сторону до ближайшего целого.
Для представленной кучи
log 2 (10+1) = 3,46 = 4
Способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма оценивается как
N·log 2 N .
Можно построить кучу за N шагов. Для этого сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод упорядочения для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
Потомки гарантированно есть у первых heapSize/2 вершин, где heapSize – размер кучи.
Реализация класса кучи
class Heap {
Static const int SIZE = 100; // максимальный размер кучи
Int *h; // указатель на массив кучи
Int
HeapSize; // размер кучи
public
:
Heap(); // конструктор кучи
Void addelem(int ); // добавление элемента кучи
Void outHeap(); // вывод элементов кучи в форме кучи
Void out(); // вывод элементов кучи в форме массива
Int getmax(); // удаление вершины (максимального элемента)
Void
heapify(int
); // упорядочение кучи
};
Конструктор кучи
h = new int ;
HeapSize = 0;
}
Новый элемент добавляется на последнее место в массиве, то есть позицию с максимальным индексом.
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае новый элемент «поднимается» на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи.
Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна log 2 N.
void Heap:: addelem(int n) {
Int i, parent;
parent = (i-1)/2;
while (parent >= 0 && i > 0) {
if (h[i] > h) {
int temp = h[i];
h[i] = h;
h = temp;
parent = (i-1)/2;
HeapSize++;
}
Вывод элементов кучи
Вывод элементов в форме кучи
void Heap:: outHeap(void ) {
Int i = 0;
Int k = 1;
While (i < HeapSize) {
while ((i < k) && (i < HeapSize)) {
cout << h[i] << » « ;
cout << endl;
Вывод элементов кучи в форме массива
void Heap:: out(void ) {
For (int i=0; i< HeapSize; i++) {
cout << h[i] << » « ; }
cout << endl;
}
Упорядочение кучи
void Heap:: heapify(int i) {
int left, right;
Int temp;
if (left < HeapSize) {
if (h[i] < h) {
if (right < HeapSize) {
if (h[i] < h) {
h[i] = h;
h = temp;
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.
Удаление вершины кучи (максимального элемента)
int Heap:: getmax(void ) {
Int x;
Чего-либо, обычно сыпучего, мелкого, наваленного, насыпанного в одном местечего-либо.
- Куча песка.
- Его одежда валялась на полу бесформенной кучей .
- Не представляю, как люди жили в коммуналках в одной куче , дети, однако же, были, и много детей, все делали в спешке, где уж тут до взаимной психотерапии, подготовки, ласк, слов.
- Эта шуба кучу денег стоит!
- Моего друга зовут Куча .
- Мою подругу зовут Куча .
Синонимы к слову куча
- груда
- масса
- скопище
- толпа
Гиперонимы к слову куча
Однокоренные слова для куча
прилагательные
- кучный
умласк
- кучка
Фразеологизмы для слова куча
- куча мала
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях - я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек
Стек - это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека - это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом - но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча
Куча - это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями - это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности - если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек - это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей - она позволяет создавать динамические и глобальные переменные - но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
указатель всего лишь указывает на область памяти, в которой хранится переменная. Это свойство указателя очень полезно, но есть еще одно, гораздо чаще применяемое в программировании. Указатель позволяет осуществить динамическое выделение памяти.
примитивные типы данных имеют определенный размер памяти, разнящийся лишь от варианта платформы.
Узнать его можно используя функцию sizeof ()
.
Структуры и классы, о которых мы поговорим в других уроках, занимают памяти ровно столько, сколько все типы данных, входящие в их поля.
Структура памяти
структура любой компилируемой программы такова, что состоит из=
- стека
- и остальной памяти, называемой кучей.
Стек
Стек – это специальная структура данных, предназначенная для быстрого доступа к данным. Эту структуру еще часто называют LIFO (Last In First Out)– последним пришел, первым ушел.
Стек представляет собой, как бы обойму, в которую вместо патрона загоняется очередная переменная.
В силу своей природы стековая память работает гораздо быстрее, чем обычная.
Стек многим хорош, но вот у него есть маленькая проблема – ограниченный объем памяти.
Примитивные типы данных занимают мало памяти и поэтому помещение их в стек является логически правильным решением, ускоряющим работу программы
.
Однако в C++, равно как и в других компилируемых языках, существуют громоздкие типы данных типа =
- массивов,
- структур
- и классов.
Переменные этих типов могут занимать обширные области памяти, что может привести к переполнению стека и экстренному прекращению работы вашей программы
.
Это очень неприятный момент в кодировании. Чтобы избежать подобной участи, была придумана концепция размещения таких громоздких типов данных в свободной области памяти, именуемой кучей
.
