高级数据结构：K-ary堆原理和实现代码详解

先决条件–二叉堆

K-ary堆是二叉堆(K = 2)的概括, 其中每个节点都有K个子节点, 而不是2个子节点。就像二叉堆一样, 它具有两个属性：

1)几乎完整的二叉树, 所有级别的节点数除最后一个节点外(从左到右填充)都最大。

2)与Binary Heap一样, 它可以分为两类：(a)最大K-ary堆(根节点的密钥大于所有后代, 并且对所有节点递归地适用)。 (b)最小k进制堆(根节点的密钥小于所有后代, 并且对所有节点递归地适用)

例子：

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

具有n个节点的完整k元树的高度由log给出ķn.

K-ary堆的应用:

• K-ary堆在执行时使用优先队列与二叉堆相比, 允许更快的减少键操作(O(log2n))对于二叉堆vs O(logķn)对于K-ary堆)。但是, 这导致extractMin()操作的复杂度增加到O(k logķn)与O(log2n)将二叉堆用于优先级队列时。这使得K-ary堆在算法中效率更高, 在这些算法中, 优先级降低操作比extractMin()操作更常见。迪克斯特拉的单源最短路径和普里姆斯最小生成树算法
• K-ary堆比二叉堆具有更好的内存缓存行为, 这使它们在实践中可以更快地运行, 尽管它在extractMin()和delete()操作的最坏情况下的运行时间都更长(两者均为O(k logķn))。

实现

假设基于0的数组索引, 则数组表示一个K-ary堆, 因此对于任何节点, 我们考虑：

• 索引i的节点(根节点除外)的父节点位于索引(i-1)/ k
• 索引为i的节点的子代的索引为(k * i)+1, (k * i)+2…。 (k * i)+ k
• 大小为n的堆的最后一个非叶子节点位于索引(n-2)/ k

buildHeap()：从输入数组构建堆。

该函数从最后一个非叶子节点一直到根节点运行一个循环, 为每个索引调用函数restoreDown(也称为maHeapify), 该函数通过移动节点将传递的索引恢复到堆的正确位置向下在K-ary堆中以自底向上的方式进行构建。

为什么我们从最后一个非叶子节点开始循环？

因为此后的所有节点都是叶节点, 它们将不满足任何子级的要求, 因此可以满足堆属性, 因此已经是K-ary最大堆的根。

restoreDown()(或maxHeapify)：用于维护堆属性。

它运行一个循环, 查找所有节点的所有子节点的最大值, 将其与自己的值进行比较, 如果max(所有子节点的值)>(节点的值), 则交换该值。重复此步骤, 直到节点恢复到堆中的原始位置。

extractMax()：提取根节点。

K元最大堆将最大元素存储在其根中。它返回根节点, 将最后一个节点复制到第一个节点, 调用在第一个节点上还原, 从而保持堆属性。

insert() ：将节点插入堆中

这可以通过在最后位置插入节点并在给定索引上调用restoreUp()来将节点恢复到堆中的适当位置来实现。 restoreUp()迭代地将给定节点与其父节点进行比较, 因为在最大堆中, 父节点始终大于或等于其子节点, 因此仅当其键大于父节点时, 节点才会与其父节点交换。

结合以上内容, 以下是K-ary堆的C++实现。

//C++ program to demonstrate all operations of
//k-ary Heap
#include<bits/stdc++.h>
  
using namespace std;
  
//function to heapify (or restore the max- heap
//property). This is used to build a k-ary heap
//and in extractMin()
//att[] -- Array that stores heap
//len   -- Size of array
//index -- index of element to be restored
//      (or heapified)
void restoreDown( int arr[], int len, int index, int k)
{
     //child array to store indexes of all
     //the children of given node
     int child[k+1];
  
     while (1)
     {
         //child[i]=-1 if the node is a leaf
         //children (no children)
         for ( int i=1; i<=k; i++)
             child[i] = ((k*index + i) <len) ?
                     (k*index + i) : -1;
  
         //max_child stores the maximum child and
         //max_child_index holds its index
         int max_child = -1, max_child_index ;
  
         //loop to find the maximum of all
         //the children of a given node
         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]];
             }
         }
  
         //leaf node
         if (max_child == -1)
             break ;
  
         //swap only if the key of max_child_index
         //is greater than the key of node
         if (arr[index] <arr[max_child_index])
             swap(arr[index], arr[max_child_index]);
  
         index = max_child_index;
     }
}
  
//Restores a given node up in the heap. This is used
//in decreaseKey() and insert()
void restoreUp( int arr[], int index, int k)
{
     //parent stores the index of the parent variable
     //of the node
     int parent = (index-1)/k;
  
     //Loop should only run till root node in case the
     //element inserted is the maximum restore up will
     //send it to the root node
     while (parent>=0)
     {
         if (arr[index]> arr[parent])
         {
             swap(arr[index], arr[parent]);
             index = parent;
             parent = (index -1)/k;
         }
  
         //node has been restored at the correct position
         else
             break ;
     }
}
  
//Function to build a heap of arr[0..n-1] and alue of k.
void buildHeap( int arr[], int n, int k)
{
     //Heapify all internal nodes starting from last
     //non-leaf node all the way upto the root node
     //and calling restore down on each
     for ( int i= (n-1)/k; i>=0; i--)
         restoreDown(arr, n, i, k);
}
  
//Function to insert a value in a heap. Parameters are
//the array, size of heap, value k and the element to
//be inserted
void insert( int arr[], int * n, int k, int elem)
{
     //Put the new element in the last position
     arr[*n] = elem;
  
     //Increase heap size by 1
     *n = *n+1;
  
     //Call restoreUp on the last index
     restoreUp(arr, *n-1, k);
}
  
//Function that returns the key of root node of
//the heap and then restores the heap property
//of the remaining nodes
int extractMax( int arr[], int * n, int k)
{
     //Stores the key of root node to be returned
     int max = arr[0];
  
     //Copy the last node's key to the root node
     arr[0] = arr[*n-1];
  
     //Decrease heap size by 1
     *n = *n-1;
  
     //Call restoreDown on the root node to restore
     //it to the correct position in the heap
     restoreDown(arr, *n, 0, k);
  
     return max;
}
  
//Driver program
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

时间复杂度分析

• 对于一个有n个节点的k元堆，给定堆的最大高度将是logkn。因此，restoreUp()运行最大的logkn时间(在每次迭代中，restoreUp()将节点向上移动一级，restoreDown则向下移动一级)。
• restoreDown()递归地为k个孩子调用自身。所以这个函数的时间复杂度是O(k logķn)。
• Insert和reduceKey()操作一次调用restoreUp()。所以复杂度是O(logķn)。
• 由于extractMax()调用一次restoreDown(), 其复杂度为O(k logķn)
• 构建堆的时间复杂度为O(n)(分析类似于二叉堆)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。