高级数据结构（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 /|\ 798 /| \/ 465 73-ary min heap -root node is minimum of all nodes 10 /|\ 121113 /| \ 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 10Heap after extract max: 9 8 6 7 3 4 5

【高级数据结构（K-ary堆原理和实现代码详解）】时间复杂度分析

对于一个有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)(分析类似于二叉堆)

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