Введение в кучу — учебные пособия по структуре данных и алгоритмам

Что такое структура данных кучи?

A Heap is a special Tree-based Data Structure in which the tree is a complete binary tree.

Типы куч:

Как правило, кучи бывают двух типов.

Макс. куча:

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

Мин-куча:

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

Характеристики кучи:

Куча имеет следующие характеристики:

• Система назначает уникальный идентификатор кучи каждой куче в группе активации. Идентификатор кучи по умолчанию всегда равен нулю. Привязываемый к управлению хранилищем API, вызываемый программой или процедурой, использует идентификатор кучи для определения кучи, с которой он должен действовать. Привязываемый API должен работать в группе активации, которой принадлежит куча.
• Размер кучи динамически увеличивается для удовлетворения запросов на выделение. Максимальный размер кучи (4 ГБ — 512 КБ) . Это максимальный размер кучи, если общее количество выделений памяти (в любой момент времени) не превышает 128 000 .
• Максимальный размер любого отдельного выделения из кучи ограничен (16 МБ — 64 КБ) .

Операции, поддерживаемые кучей:

Operations supported by min – heap and max – heap are same. The difference is just that min-heap contains minimum element at root of the tree and max – heap contains maximum element at the root of the tree.

Огромный:

Это процесс перестановки элементов для сохранения свойства кучи структуры данных. Это делается, когда определенный узел создает дисбаланс в куче из-за некоторых операций на этом узле. Требуется O (log N), чтобы сбалансировать дерево.

• Для max-heap он балансируется таким образом, что максимальный элемент является корнем этого двоичного дерева, а
• Для min-heap он уравновешивается таким образом, что минимальный элемент является корнем этого двоичного дерева.

Вставка:

• Если мы вставляем новый элемент в кучу, поскольку мы добавляем новый элемент в кучу, это искажает свойства кучи, поэтому нам нужно выполнить операцию heapify , чтобы она поддерживала свойство кучи.

Эта операция также занимает время O(logN) .

Примеры:

Assume initially heap(taking max-heap) is as follows

           8
        /  
     4     5
   /
1   2

Now if we insert 10 into the heap
             8
        /      
      4       5
   /        /
1    2  10 

After heapify operation final heap will be look like this
           10
         /    
      4      8
   /       /
1    2  5

Удаление:

• Если мы удаляем элемент из кучи, он всегда удаляет корневой элемент дерева и заменяет его последним элементом дерева.
• Поскольку мы удаляем корневой элемент из кучи, это искажает свойства кучи, поэтому нам нужно выполнять операции кучи, чтобы он поддерживал свойство кучи.

Это занимает O(logN) времени.

Пример:

Assume initially heap(taking max-heap) is as follows
           15
         /  
      5     7
   /  
2     3

Now if we delete 15 into the heap it will be replaced by leaf node of the tree for temporary.
           3
        /  
     5     7
   /    
2

After heapify operation final heap will be look like this
           7
        /  
     5     3
   /   
2

getMax (для максимальной кучи) или getMin (для минимальной кучи):

Он находит максимальный элемент или минимальный элемент для максимальной кучи и минимальной кучи соответственно, и, как мы знаем, минимальный и максимальный элементы всегда будут самим корневым узлом для минимальной кучи и максимальной кучи соответственно. Это занимает O(1) времени.

удалитьМин или удалитьМакс:

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

Реализация структуры данных кучи: -

В следующем коде показана реализация max-heap .

Давайте подробно разберем функцию maxHeapify :

maxHeapify — это функция, отвечающая за восстановление свойства Max Heap. Он упорядочивает узел i и его поддеревья соответственно, чтобы сохранить свойство кучи.

1. Предположим, нам дан массив arr[] , представляющий полное бинарное дерево. Левый и правый потомки i ^- го узла находятся в индексах 2*i+1 и 2*i+2 .
2. Мы устанавливаем индекс текущего элемента i как «МАКСИМАЛЬНЫЙ».
3. Если arr[2 * i + 1] > arr[i] , т. е. левый дочерний элемент больше текущего значения, он устанавливается как «МАКСИМАЛЬНЫЙ».
4. Точно так же, если arr[2 * i + 2] > arr[i] , т. е. правый дочерний элемент больше текущего значения, он устанавливается как «МАКСИМАЛЬНЫЙ».
5. Поменяйте местами «МАКСИМУМ» с текущим элементом.
6. Повторяйте шаги со 2 по 5, пока свойство кучи не будет восстановлено.

Применение структуры данных кучи:

• Очереди с приоритетом: Очереди с приоритетом могут быть эффективно реализованы с использованием двоичной кучи, поскольку она поддерживает операции вставки (), удаления () и извлечения макс (), уменьшение ключа () за время O (log N) .
• Биномиальная куча и куча Фибоначчи являются вариациями двоичной кучи. Эти варианты также выполняют объединение за время O(log N) , что является операцией O(N) в двоичной куче.
• Статистика порядка: структуру данных кучи можно использовать для эффективного поиска k-го наименьшего (или самого большого) элемента в массиве. Вы можете прочитать эту статью gfg, чтобы узнать больше о k-м наименьшем или самом большом элементе.