d叉堆的实现相对于二叉堆变化不大，首先看它如何用数组表示。
考虑一个索引从1开始的数组，一个结点i最多可以有d个子结点，编号从id - (d - 2) 到 id + 1。
从而可以知道一个结点i的父结点计算方法为: （i + d - 2） / d。
第二个问题是 一个含有n个元素的d叉堆的高度，就是一个简单的等比数列的问题，可以知道的是一颗高度为h的满d叉树所含的结点数目为(d^(h +１) - 1) / (d - 1)
从而一颗含有 n个结点的d叉树满足的条件为：
，从而得到高度h为：
接下来三个小问的实现思路就跟书中的伪码大同小异了，直接附上源码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int d = 5;
#define PARENT(i) (i + d - 2) / d
#define child(k) -(d - 2) + k - 1
void max_heapify(int A[], int i, int &size){
int largest = i;
for (int k = 1; k <= d; k ++){
int child = i + child(k);
if (child <= size && A[child] > A[largest])
largest = child;
}
if (largest != i) {
swap(A[i], A[largest]);
max_heapify(A, largest, size);
}
}
int heap_extract_max(int A[], int &size){
if (size < 1)
return -1;
int max = A[1];
A[1] = A[size];
size--;
max_heapify(A, 1, size);
return max;
}
void heap_increase_key(int A[], int i, int key){
if (key <= A[i]) return;
A[i] = key;
while (i > 1 && A[PARENT(i)] < A[i]){
swap(A[i], A[PARENT(i)]);
i = PARENT(i);
}
}
void max_heap_insert(int A[], int &size, int key){
size++;
A[size] = INT_MIN;
heap_increase_key(A, size, key);
}