首页 > 代码库 > 算法导论 第六章 思考题 6-3 d叉堆
算法导论 第六章 思考题 6-3 d叉堆
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 - 1void 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);}
算法导论 第六章 思考题 6-3 d叉堆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。