Рубрики

К-рый Куча

Обязательное условие — двоичная куча

K-арные кучи являются обобщением двоичной кучи (K = 2), в которой каждый узел имеет K дочерних элементов вместо 2. Так же, как и двоичная куча, он имеет два свойства:

1) Почти полное двоичное дерево со всеми уровнями, имеющими максимальное количество узлов, кроме последнего, которое заполняется слева направо.

2) Как и Binary Heap, его можно разделить на две категории: (a) Max k-ary heap (ключ в корне больше, чем все потомки, и то же самое рекурсивно верно для всех узлов). (b) Min k-ary куча (ключ в корне меньше всех потомков и то же самое рекурсивно верно для всех узлов)

Примеры:

3-ary max heap - root node is maximum
                 of all nodes
         10
     /    |   \
   7      9     8
 / | \   /
4  6  5 7


3-ary min heap -root node is minimum 
                of all nodes
         10
      /   |  \
    12    11  13
  / | \
14 15 18 

Высота полного k-арного дерева с n-узлами определяется как log k n.

Применение K-арой кучи :

  • K-арная куча при использовании в реализации очереди приоритетов позволяет быстрее уменьшить операции с ключами по сравнению с двоичной кучей (O (log 2 n)) для двоичной кучи по сравнению с O (log k n) для K-арной кучи). Тем не менее, это вызывает сложность операции extractMin () , чтобы увеличить до O (к логу к п) по сравнению со сложностью O (вход 2 N) при использовании двоичных куч для приоритетной очереди. Это позволяет более эффективно использовать K-арную кучу в алгоритмах, где операции с уменьшением приоритета встречаются чаще, чем операция extractMin (). Пример: алгоритм Дейкстры для кратчайшего пути с одним источником и алгоритм Прима для минимального остовного дерева
  • K-арная куча имеет лучшее поведение кеша памяти, чем двоичная куча, что позволяет им работать быстрее на практике, хотя в худшем случае она имеет большее время выполнения операций extractMin () и delete () (обе являются O (k log k). н)).

Реализация
Предполагая индексирование массива на основе 0, массив представляет K-арную кучу, такую что для любого рассматриваемого нами узла:

  • Родитель узла по индексу i (кроме корневого узла) находится по индексу (i-1) / k
  • Дочерние узлы в индексе i имеют индексы (k * i) +1, (k * i) +2…. (К * я) + K
  • Последний неконечный узел кучи размера n находится с индексом (n-2) / k

buildHeap () : строит кучу из входного массива.
Эта функция запускает цикл, начиная с последнего неконечного узла, вплоть до корневого узла, вызывая функцию restoreDown (также известную как maHeapify) для каждого индекса, который восстанавливает переданный индекс в правильной позиции кучи путем сдвига узла вниз, в куче К-ар, строя его снизу вверх.
Почему мы начинаем цикл с последнего неконечного узла?
Потому что все узлы после этого являются листовыми узлами, которые будут тривиально удовлетворять свойству кучи, так как у них нет дочерних элементов и, следовательно, уже являются корнями K-арной максимальной кучи.

restoreDown () (или maxHeapify) : используется для поддержки свойства кучи.
Он запускает цикл, где находит максимум всех дочерних узлов, сравнивает его со своим собственным значением и меняет местами, если max (значение всех дочерних элементов)> (значение в узле). Он повторяет этот шаг до тех пор, пока узел не будет восстановлен в своем первоначальном положении в куче.

extractMax (): извлечение корневого узла.
В куче k-ary max хранится самый большой элемент в его корне. Он возвращает корневой узел, копирует последний узел в первый, вызывает восстановление на первом узле, таким образом сохраняя свойство кучи.

insert (): вставка узла в кучу
Это может быть достигнуто путем вставки узла в последнюю позицию и вызова restoreUp () для данного индекса, чтобы восстановить узел в его правильном положении в куче. restoreUp () итеративно сравнивает данный узел с его родителем, поскольку в максимальной куче родительский узел всегда больше или равен его дочерним узлам, узел заменяется своим родителем только тогда, когда его ключ больше родительского.

Комбинируя вышесказанное, ниже следует реализация K-арной кучи на C ++.

// C ++ программа для демонстрации всех операций
// К-рый Куча
#include<bits/stdc++.h>

  

using namespace std;

  
// функция для кучи (или восстановления максимальной кучи
// свойство). Это используется для построения k-арной кучи
// и в extractMin ()
// att [] - Массив, в котором хранится куча
// len - размер массива
// index - индекс элемента, который будет восстановлен
// (или куча)

void restoreDown(int arr[], int len, int index,

                                        int k)

{

    // дочерний массив для хранения индексов всех

    // дети данного узла

    int child[k+1];

  

    while (1)

    {

        // child [i] = - 1, если узел является листом

        // дети (без детей)

        for (int i=1; i<=k; i++)

            child[i] = ((k*index + i) < len) ?

                    (k*index + i) : -1;

  

        // max_child хранит максимальный дочерний элемент и

        // max_child_index содержит свой индекс

        int max_child = -1, max_child_index ;

  

        // цикл, чтобы найти максимум всех

        // дети данного узла

        for (int i=1; i<=k; i++)

        {

            if (child[i] != -1 &&

                arr[child[i]] > max_child)

            {

                max_child_index = child[i];

                max_child = arr[child[i]];

            }

        }

  

        // листовой узел

        if (max_child == -1)

            break;

  

        // меняем местами только если ключ max_child_index

        // больше ключа узла

        if (arr[index] < arr[max_child_index])

            swap(arr[index], arr[max_child_index]);

  

        index = max_child_index;

    }

}

  
// Восстанавливает данный узел в куче. Это используется
// в lowerKey () и insert ()

void restoreUp(int arr[], int index, int k)

{

    // parent хранит индекс родительской переменной

    // узла

    int parent = (index-1)/k;

  

    // Цикл должен выполняться только до корневого узла, если

    // вставленный элемент - максимальное восстановление

    // отправить его в корневой узел

    while (parent>=0)

    {

        if (arr[index] > arr[parent])

        {

            swap(arr[index], arr[parent]);

            index = parent;

            parent = (index -1)/k;

        }

  

        // узел восстановлен в правильном положении

        else

            break;

    }

}

  
// Функция для построения кучи arr [0..n-1] и alue из k.

void buildHeap(int arr[], int n, int k)

{

    // Heapify всех внутренних узлов, начиная с последнего

    // неконечный узел вплоть до корневого узла

    // и вызываем восстановление на каждом

    for (int i= (n-1)/k; i>=0; i--)

        restoreDown(arr, n, i, k);

}

  
// Функция для вставки значения в кучу. Параметры
// массив, размер кучи, значение k и элемент для
// быть вставленным

void insert(int arr[], int* n, int k, int elem)

{

    // Поместить новый элемент в последнюю позицию

    arr[*n] = elem;

  

    // Увеличить размер кучи на 1

    *n = *n+1;

  

    // Вызовите restoreUp по последнему индексу

    restoreUp(arr, *n-1, k);

}

  
// Функция, которая возвращает ключ корневого узла
// куча, а затем восстанавливает свойство кучи
// оставшихся узлов

int extractMax(int arr[], int* n, int k)

{

    // Сохраняет ключ корневого узла, который будет возвращен

    int max = arr[0];

  

    // Копируем ключ последнего узла в корневой узел

    arr[0] = arr[*n-1];

  

    // Уменьшаем размер кучи на 1

    *n = *n-1;

  

    // Вызовите restoreDown на корневом узле для восстановления

    // это в правильную позицию в куче

    restoreDown(arr, *n, 0, k);

  

    return max;

}

  
// Драйвер программы

int main()

{

    const int capacity = 100;

    int arr[capacity] = {4, 5, 6, 7, 8, 9, 10};

    int n = 7;

    int k = 3;

  

    buildHeap(arr, n, k);

  

    printf("Built Heap : \n");

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

  

    int element = 3;

    insert(arr, &n, k, element);

  

    printf("\n\nHeap after insertion of %d: \n",

            element);

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

  

    printf("\n\nExtracted max is %d",

                   extractMax(arr, &n, k));

  

    printf("\n\nHeap after extract max: \n");

    for (int i=0; i<n; i++)

        printf("%d ", arr[i]);

  

    return 0;

}

Выход

Built Heap : 
10 9 6 7 8 4 5 

Heap after insertion of 3: 
10 9 6 7 8 4 5 3 

Extracted max is 10

Heap after extract max: 
9 8 6 7 3 4 5 

Анализ сложности времени

  • Для k-арной кучи с n узлами максимальная высота данной кучи будет log k n. Таким образом, restoreUp () запускается максимум из журнала k n раз (так как на каждой итерации узел перемещается на один уровень вверх в случае restoreUp () или на один уровень вниз в случае restoreDown).
  • restoreDown () вызывает себя рекурсивно для k детей. Таким образом, временная сложность этой функции составляет O (k log k n).
  • Операции вставки и уменьшения ключа () вызывают restoreUp () один раз. Таким образом , сложность О (лог к п).
  • Поскольку extractMax () вызывает restoreDown () один раз, его сложность O (k log k n)
  • Временная сложность сборки кучи составляет O (n) (анализ аналогичен двоичной кучи)

Эта статья предоставлена Анураг Рай . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

К-рый Куча

0.00 (0%) 0 votes