算导学习——d叉堆

  1. 1. 算导学习——d叉堆
    1. 1.1. d叉堆性质
    2. 1.2. d叉堆操作
      1. 1.2.1. 维持堆序性
      2. 1.2.2. 将数组转化为堆
      3. 1.2.3. 取出堆最大值
      4. 1.2.4. 向堆中插入元素

算导学习——d叉堆

与二叉堆类似,但d叉堆(d-ary heap)是每个非叶结点可有d个儿子。

C语言实现,为最大堆

d叉堆性质

  • 以0为根结点,对某结点 \(i\) ,其父结点为\(\lfloor (i-1)/d \rfloor\),其d个子结点范围为\((di + 1) \sim (di + d)\)

  • 包含n个元素的d叉堆的高度:\(h = \Theta(log_dn)\)

\(\text{set height of d-ary heap as }h, then\)

\(\begin{cases} 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{cases} \\\)

\(\therefore log_d(n(d-1) + 1)-1 \le h \le log_d((n-1)(d-1) + 1)\)

\(\Leftrightarrow log_d(n(d-1) + 1)-1 \le h \le log_d(n(d-1) -d + 2)\)

\(\therefore h = \lceil log_d(n(d-1) + 1) -1 \rceil\)

\(as\ h = \Theta(log_d{n})\)

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

\(\text{set the maximum of subscript as } x, then\)

\(x = d^0 + d^1 + d^2 + \cdots + d^{h-1}\)

\(also \ log_d(n(d-1) + 1)-1 \le h \le log_d(n(d-1) -d + 2)\)

\(so, \frac{n-1}{d} \le x \le n-1\)

\(\Rightarrow x = \lceil \frac{n-1}{d} \rceil\)

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

as the whole leaf nodes are the child nodes about one of the specific son node given the numbers of all the nodes and all the specific child heap nodes are separately \(n, x , then\) \[ \begin{cases} 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{cases} \\\\ \Rightarrow x = \frac{dn-1}{2d-1} \]

d叉堆操作

d叉堆定义如下:

1
2
3
4
5
6
7
struct heap {
int size;
int length;
ElementType *elements;
};

typedef struct heap *Heap;

其中length为数组长度,而size为堆的元素个数

维持堆序性

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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}\)个结点。

故可写出递归关系式:

\(T(n) = \begin{cases} \Theta(d) \quad n=1 \\ T(\frac{dn-1}{2d-1}n) + \Theta(d) \quad n \ge 2 \end{cases}\)

\(\text{as Master Theorem}\)

\(T(n) = \Theta(d \cdot log_dn)\)

将数组转化为堆

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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->length = 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_dn)\)

取出堆最大值

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ElementType ExtractMax(Heap heap) {

if(heap == NULL || heap->elements == NULL){
printf("heap or elements is error!");
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_dn)\)

向堆中插入元素

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

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

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

此过程称上滤(percolate up)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Insert(Heap heap, ElementType ele) {

if (heap->size == heap->length) {
printf("error the heap is full!");
return;
}

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;
}

此过程最差情况下的时间复杂度为:\(\Theta(log_dn)\)