東京大学 情報理工学系研究科 コンピュータ科学専攻 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)

The following arrays list nodes level by level from left to right, so each row specifies the complete heap tree at that step.

Step	Level-order array
Initial heap	[23,48,29,63,54,31]
Append 21	[23,48,29,63,54,31,21]
Swap 21 with 29	[23,48,21,63,54,31,29]
Swap 21 with 23	[21,48,23,63,54,31,29]
Append 26	[21,48,23,63,54,31,29,26]
Swap 26 with 63	[21,48,23,26,54,31,29,63]
Swap 26 with 48	[21,26,23,48,54,31,29,63]

The final tree is

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

(2)

Step	Level-order array
Initial heap	[21,25,42,55,48,73]
Remove 21; move the last element to the root	[73,25,42,55,48]
Swap 73 with 25	[25,73,42,55,48]
Swap 73 with 48	[25,48,42,55,73]
Remove 25; move the last element to the root	[73,48,42,55]
Swap 73 with 42	[42,48,73,55]

The final tree is

        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 first 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 the root value with the last element in the heap array (and we erase that element). Then, we need to "bubble down" this element. For $n\ge2$, at each iteration we inspect the existing 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 worst-case number of visited nodes is $\Theta(\log n)$; removing the only node takes constant time.

(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.