d叉堆性质

以0为根结点，对某结点 \(i\) ,其父结点为 \(\lfloor \frac{i-1}{d} \rfloor\) ，其d个子结点范围为 \([ (di+1), (di+d) ]\)
包含n个元素的d叉堆的高度：\(h=\Theta(log_d(n))\). 证明如下:

\[\mbox{assume the height of d-ary heap with } n \mbox{ elements as } h \mbox{ , then} \\ \begin{equation} \left\{ \begin{array}{ll} n \ge d^{0} + d^{1} + d^{2} + \cdots + d^{h-1} + 1 \\ n \le d^{0} + d^{1} + d^{2} + \cdots + d^{h} \end{array} \right. \end{equation} \\ \Rightarrow log_{d}( n(d-1) + 1 ) - 1 \le h \le lod_{d}((n-1)(d-1) + 1) \\ \Rightarrow log_{d}(n(d-1)+1) - 1 \le h \le log_{d}(n(d-1) -d + 2) \\ \Rightarrow h = \lceil log_{d}(n(d-1)+1) - 1 \rceil \\ \Rightarrow h = \Theta(log_{d}(n))\]

非叶子节点的最大下标 \(x = \lceil \frac{n-1}{d} \rceil\), 证明如下:

\[\mbox{set the maximum os subscript as } x \mbox{ , then} \\ x = d^{0} + d^{1} + d^{2} + \cdots + d^{h-1} \\ \mbox{also, } log_{d}(n(d-1)+1) - 1 \le h \le log_{d}(n(d-1) -d + 2) \\ \mbox{therefore, } \frac{n-1}{d} \le x \le n - 1 \\ \Rightarrow x = \lceil \frac{n-1}{d} \rceil\]

一d叉堆中，根节点的一个子树最多有 \(x=\frac{dn-1}{2d-1}\) 个结点

\[\mbox{as the whole leaf nodes are the child nodes of one of the specific child node} \\ \mbox{assume the numbers of all the nodes and all the specific sub-heap nodes are separately } n, x \mbox{ , then} \\ \begin{equation} \left\{ \begin{array}{ll} n = d^{0} + d^{1} + d^{2} + \cdots + d^{h-1} + d^{h-1} \\ x = d^{0} + d^{2} + d^{3} + \cdots + d^{h-2} + d^{h-1} \end{array} \right. \end{equation} \\ \Rightarrow x = \frac{dn-1}{2d-1}\]

d叉堆操作

定义d叉堆数据结构如下:

struct heap {
    int size;   // the number of heap elements
    int cap; // array length
    ElementType *elements;
};

typedef struct heap *Heap;

维持堆序性

适用范围：某结点 \(i\) 的子结点满足堆序性，使含 \(i\) 也满足堆序性。

方法为在结点 \(i\) 及其子结点中寻找到最大的值。如果 \(i\) 即最大值，则整个堆满足堆序性，任务完成。

若其中一个子结点比 \(i\) 大，则交换二者的值，此时该子堆的顶为最大，而交换后的那个子结点可能不满足堆序性，故递归操作，直至整个堆都满足堆序性。

void MakeHeapify(Heap heap, int i) {
    int child, largest = i;

    for (int j = 0; j < d; ++j) {
        child = d * i + 1 + j;
        if ((child < heap->size) && (heap->elements[child] > heap->elements[largest])) {
            largest = child;
        }
    }

    // it means the ith element is the largest,
    // so the heap satisfies the heap order
    if (largest == i) {
        return;
    }

    // exchange the elements between the ith and the largest
    ElementType temp = heap->elements[i];
    heap->elements[i] = heap->elements[largest];
    heap->elements[largest] = temp;

    MakeHeapify(heap, largest);
}

分析该函数的最差情况下的时间复杂度：

获取节点 \(i\) 及其所有子结点的最大值时，时间复杂度为 \(\Theta(d)\)

判断递归出口，时间复杂度为 \(\Theta(1)\)

在递归过程中，\(i\) 的一个子树最多可以获得 \(\frac{dn-1}{2d-1}\) 个结点。

故可写出递归关系式：

\[\begin{equation} T(n) = \left\{ \begin{array}{ll} \Theta(1) & n = 1 \\ T(\frac{dn-1}{2d-1}n) + \Theta(d) & n \ge 2 \end{array} \right. \end{equation} \\ \mbox{as Master Theorem} \\ T(n) = \Theta(d \cdot log_{d}(n))\]

将数组转化为堆

非叶结点最大下标为： \(x=\lceil \frac{n-1}{d} \rceil\), 即当下标 \(i > \lceil \frac{n-1}{d} \rceil\)，则均为叶结点。而叶结点为高为0的堆，满足堆序性。故从 \(i \ from \ \lceil \frac{n-1}{d} \rceil \ down \ to \ 0\),每一结点使其满足堆序性。则整个数组最后满足堆序性，为一最大堆。

其中，尤其要注意的是，不能直接将ele赋值给heap->elements。因为这样，ele中元素改变时，heap->elements中的元素也会改变。

Heap ConvertArrayToHeap(const ElementType ele[], int n) {
    Heap heap = (Heap) malloc(sizeof(struct heap));
    if (heap == NULL) {
        printf("malloc error! out of space");
        return NULL;
    }
    heap->size = n;
    heap->cap = n;

    ElementType *elements = (ElementType *) malloc(sizeof(ElementType) * n);
    if (elements == NULL) {
        printf("malloc error! out of space");
        return NULL;
    }

    for (int i = 0; i < n; ++i) {
        elements[i] = ele[i];
    }
    heap->elements = elements;

    for (int i = (n - 1 + d) / d; i >= 0; --i) {
        MakeHeapify(heap, i);
    }

    return heap;
}

该函数的最差情况下的时间复杂度： \(T(n) = \Theta(n \cdot log_{d}(n) )\)

取出堆最大值

根据堆序性，elements数组中的第一个元素即为最大值。我们去掉这个元素后，可以采用将elements数组中最后一个元素放置在一个元素位上，此时肯定是不满足堆序性的。但通过MakeHeapify使其满足堆序性。此时便得到了去掉最大值后的新的最大堆。

ElementType ExtractMax(Heap heap) {
    if(heap == NULL || heap->elements == NULL){
        printf("heap or elements is nil!");
        return INF;
    }
    
    ElementType max = heap->elements[0];

    heap->elements[0] = heap->elements[--heap->size];

    MakeHeapify(heap, 0);

    return max;
}

该函数的最差情况下的时间复杂度： \(T(n) = \Theta( d \cdot log_{d}(n) )\)

向堆中插入元素

将需要插入的元素插入进elements数组的最后一个元素（如果未满）。

此时如果该元素 \(i\) 小于其父节点 \(p\)，则该堆满足堆序性，插入完成。

如果大于，则交换该结点与 \(p\)，此时该子堆满足堆序性。但是交换后的i的父结点可能不满足堆序性，故递归操作，直至整个堆满足堆序性。

此过程称上滤（percolate up）。

其中，采用类似插入排序内层循环的方式，避免了多次交换。仅通过一次赋值完成被插入元素的

int Insert(Heap heap, ElementType ele) {
    if (heap->size == heap->cap) {
        printf("the heap is full!");
        return 1;
    }

    int child = heap->size, parent = (child - 1) / d;

    heap->elements[heap->size++] = ele;

    while (child > 0 && (ele > heap->elements[parent])) {
        heap->elements[child] = heap->elements[parent];

        child = parent;
        parent = (child - 1) / d;
    }

    heap->elements[child] = ele;

    return 0;
}

此过程最差情况下的时间复杂度为： \(T(n) = \Theta( log_{d}(n) )\)

Reference

算法导论