Skip to content

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

Author

kainoj

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.

1
2
3
4
5
     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.

1
2
3
4
5
     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.

Kai

(1)

After inserting \(21, 26\), the heap should look like:

1
2
3
4
5
6
7
        21
      /    \
    26      23
   /  \    /  \
 48   54  31   29
 |
 63

(2)

After delete-min the heap should look like:

1
2
3
4
5
        25
      /    \
    48      42
   /  \
 35   73

(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 other \(n\) elements, then we'll traverse whole tree. That means we will visit around \(\lfloor \log_2 (n+1)\rfloor\) elements.

(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'll visit its both children. In worst case, we'll bubble it down to the deepest level. So, we'll visit no more than \(2 \lfloor \log_2 (n-1) \rfloor\) elements.

(5)

Maximum element will reside somewhere on the deepest level, and we need to visit them all. There are no more than \(\lceil \frac{n}{2} \rceil\) elements on the deepest level.