跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問8

标签：

Author​

GPT-5

Description​

A nearly complete binary tree is filled on all levels except possibly the deepest, which is filled from the left. Indexing its nodes from 0 in level order gives an array representation AA. It is a heap when

A[parent⁡(i)]≥A[i]A[\operatorname{parent}(i)]\geq A[i]

for every non-root node ii.

Index ii0123456789
A[i]A[i]15121011897632

The height of a node is the number of edges on its longest path to a leaf. The following properties may be used.

  • (P1) The root of an nn-element heap has height ⌊log⁡2n⌋\lfloor\log_2n\rfloor.
  • (P2) The number of nodes of height hh is at most ⌈n/2h+1⌉\lceil n/2^{h+1}\rceil.

The following code constructs a heap.

void heapify(int a[], int i, int n) {
    int k = 2*i+1;             /* node k is the left child of node i */
    while (k < n) {
        if (k+1 < n && a[k+1] > a[k]) k = k+1;
        if (a[i] >= a[k]) return;
        int tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
        i = k; k = 2*i+1;
    }
}

void build_heap(int a[], int n) {
    for (int i = n-1; i >= 0; i--) {
        heapify(a, i, n);
    }
}

(1) Find the number of different 7-element heaps containing all integers from 1 to 7.

(2) Run build_heap(a1,10) for a1={2,6,7,3,9,11,8,10,15,4}a_1=\{2,6,7,3,9,11,8,10,15,4\} and give the resulting array.

(3) Explain why heapify(a,i,n) takes O(h)O(h) time for a node of height hh.

(4) Show using (P1), (P2), and ∑k=1mk/2k=2−(m+2)/2m\sum_{k=1}^m k/2^k=2-(m+2)/2^m that build_heap(a,n) takes O(n)O(n) time.

题目描述​

一棵近似完全二叉树除最深层外各层均填满，最深层的结点从左向右填充。按层序从 00 开始给结点编号，可得到数组表示 AA；若每个非根结点 ii 都满足

A[parent⁡(i)]≥A[i],A[\operatorname{parent}(i)]\geq A[i],

则称其为堆。题面给出的树形图及对应表格展示了数组

(A[0],…,A[9])=(15,12,10,11,8,9,7,6,3,2)(A[0],\ldots,A[9])=(15,12,10,11,8,9,7,6,3,2)

所表示的一个堆。结点的高度定义为从该结点到叶结点的最长路径所含边数。可以使用以下性质：

  • (P1) 含 nn 个元素的堆，其根结点高度为 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor；
  • (P2) 高度为 hh 的结点至多有 ⌈n/2h+1⌉\lceil n/2^{h+1}\rceil 个。

给定题面中的 C 代码：heapify(a,i,n) 从结点 ii 开始，反复选择两个孩子中键值较大者；若父结点已不小于它便返回，否则交换并继续向下；build_heap(a,n) 则按 i=n−1,n−2,…,0i=n-1,n-2,\ldots,0 的顺序对每个结点调用 heapify。回答：

  1. 求由整数 11 至 77 各使用一次所能构成的不同七元素堆的数量。

  2. 对

    a1={2,6,7,3,9,11,8,10,15,4}a_1=\{2,6,7,3,9,11,8,10,15,4\}

    执行 build_heap(a1,10)，写出执行结束后的数组。

  3. 说明为什么对高度为 hh 的结点，heapify(a,i,n) 的运行时间为 O(h)O(h)。

  4. 使用 (P1)、(P2) 以及

    ∑k=1mk2k=2−m+22m\sum_{k=1}^m\frac{k}{2^k}=2-\frac{m+2}{2^m}

    证明 build_heap(a,n) 的运行时间为 O(n)O(n)。

考点​

  • 二叉堆的结构与计数：利用完全二叉树形状和父结点不小于子结点的约束，计算指定键集合的合法堆数。
  • 下沉式堆化过程：逐步追踪 heapify 的比较与交换，求给定数组经自底向上建堆后的排列。
  • 建堆复杂度分析：按结点高度汇总每次下沉的代价，并结合高度结点数上界与给定级数证明总复杂度为线性级。

Kai​

(1)​

根には最大値 7 を置く必要がある。残り 6 個から左の 3 頂点部分木に置く値を選ぶ方法は (63)\binom63 通りである。各 3 頂点部分木では最大値が根に決まり、残り 2 値の左右への配置が 2 通りある。したがって

(63)⋅2⋅2=80.\boxed{\binom63\cdot2\cdot2=80}.

(2)​

値が変化する呼び出しを追うと次のようになる。

処理後配列
初期状態（i=4i=4 の処理後も同じ）{2,6,7,3,9,11,8,10,15,4}\{2,6,7,3,9,11,8,10,15,4\}
i=3i=3{2,6,7,15,9,11,8,10,3,4}\{2,6,7,15,9,11,8,10,3,4\}
i=2i=2{2,6,11,15,9,7,8,10,3,4}\{2,6,11,15,9,7,8,10,3,4\}
i=1i=1{2,15,11,10,9,7,8,6,3,4}\{2,15,11,10,9,7,8,6,3,4\}
i=0i=0{15,10,11,6,9,7,8,2,3,4}\{15,10,11,6,9,7,8,2,3,4\}

よって

a1={15,10,11,6,9,7,8,2,3,4}.\boxed{a_1=\{15,10,11,6,9,7,8,2,3,4\}}.

(3)​

ループ 1 回の比較・交換は定数時間であり、交換後は注目節点が子へ 1 段下がる。高さ hh の節点から葉まで高々 hh 段なので、反復回数は高々 hh、実行時間は O(h)O(h) である。

(4)​

H=⌊log⁡2n⌋H=\lfloor\log_2n\rfloor とし、高さ hh の節点数を NhN_h とする。葉を含む各呼び出しの定数時間を c0nc_0n、下向き処理を節点当たり c1hc_1h 以下と評価すると、(P2) より

T(n)≤c0n+c1∑h=1HNhh≤c0n+c1(n2∑h=1Hh2h+∑h=1Hh)=c0n+c1[n2(2−H+22H)+H(H+1)2].\begin{aligned} T(n) &\leq c_0n+c_1\sum_{h=1}^HN_hh\\ &\leq c_0n+c_1\left( \frac n2\sum_{h=1}^H\frac{h}{2^h}+\sum_{h=1}^Hh \right)\\ &=c_0n+c_1\left[ \frac n2\left(2-\frac{H+2}{2^H}\right)+\frac{H(H+1)}2 \right]. \end{aligned}

H=O(log⁡n)H=O(\log n) かつ (log⁡n)2=O(n)(\log n)^2=O(n) なので

T(n)=O(n).\boxed{T(n)=O(n)}.
本页目录