東京大学 情報理工学系研究科 コンピュータ科学専攻 2015年2月実施 問題3

标签：

• Tokyo-University
• Priority-Queue

Author

kainoj, 祭音Myyura

Description

Consider the implementation of a priority queue using a binary heap data structure. Note that a binary heap satisfies the following properties:

• It forms a complete binary tree. All levels except for the deepest level are full, and the deepest level is filled from left to right.
• Each node has at most two child nodes, and the number stored in a parent node is equal or smaller than the numbers stored in its children.

Answer the following questions.

(1) Suppose that you have the following binary heap.

     23
    /  \
  48    29
 /  \   /
63  54 31

Now you insert two elements, 21 and then 26, to the binary heap. Depict the step-by-step transformation of the binary heap.

(2) Suppose that you have the following binary heap.

     21
    /  \
  25    42
 /  \   /
55  48 73

Now you apply delete-min operations to the heap two times. Depict the step-by-step transformation of the binary heap.

(3) Estimate the number of nodes to be visited when inserting a node to a binary heap with $n$ nodes. Give a brief explanation.

(4) Estimate the number of nodes to be visited when applying delete-min operation to a binary heap with $n$ nodes. Give a brief explanation.

(5) Estimate the number of nodes to be visited when searching for the maximum element in a binary heap with $n$ nodes. Give a brief explanation.

题目描述

考虑用二叉堆实现优先队列。该二叉堆满足：

• 它是一棵完全二叉树：除最深层外各层均满，最深层从左到右依次填充；
• 每个结点至多有两个子结点，且父结点存放的数不大于任一子结点中的数。

回答下列问题。

（1）对题中初始二叉堆依次插入元素 $21$、$26$，画出二叉堆每一步的变化过程。

（2）对题中另一个初始二叉堆连续执行两次删除最小元素（delete-min）操作，画出二叉堆每一步的变化过程。

（3）估计向含有 $n$ 个结点的二叉堆插入一个结点时需要访问的结点数，并简述理由。

（4）估计对含有 $n$ 个结点的二叉堆执行 delete-min 时需要访问的结点数，并简述理由。

（5）估计在含有 $n$ 个结点的二叉堆中查找最大元素时需要访问的结点数，并简述理由。

Kai

(1)

Inserting $21$ gives

        21
      /    \
    48      23
   /  \    /  \
 63   54  31   29

and then inserting $26$ gives

        21
      /    \
    26      23
   /  \    /  \
 48   54  31   29
 |
 63

(2)

After the first delete-min operation:

        25
      /    \
    48      42
   /  \
 55   73

After the second:

        42
      /    \
    48      73
   /
 55

(3)

I understand visiting a node by accessing an array in which heap is stored.

To insert a node, we first put it in fist available "slot" on the deepest level and then we "bubble" it up. If the inserted element is smaller than the other $n$ elements, it is compared with every ancestor and moves along the entire leaf-to-root path. The heap height is $\lfloor\log_2(n+1)\rfloor$, so the number of visited nodes is $\Theta(\log n)$.

(4)

First we, replace value with root with the last element in the heap array (and we erase that element). Then, we need to "bubble down" this element. At each iteration we inspect both children and move to the smaller one. In the worst case the replacement reaches the deepest level, so at most two children are inspected on each of $\lfloor\log_2(n-1)\rfloor$ levels. Thus the number of visited nodes is $\Theta(\log n)$.

(5)

A maximum element is a leaf. A binary heap has exactly $\lceil n/2\rceil$ leaves, and the heap order gives no way to discard any of them. Thus $\Theta(n)$ nodes must be visited in the worst case.