東京大学 新領域創成科学研究科 メディカル情報生命専攻 2017年8月実施 問題9
Author
Description
A binary heap tree is a binary tree with integer labels such that the value of a parent node is no less than the value of any child node. We denote the height of a tree
(1) Choose all binary heap trees from the following.

(2) Suppose we have a binary tree
(3) Suppose we have two binary heap trees
(4) Suppose we have a binary tree
(5) Show an algorithm that sorts in descending order an array of integers using the operations you showed in (4). Show the worst-case time complexity of the algorithm with regard to the number of elements in the array.
二叉堆树是一种二叉树,其整数标签的值满足父节点的值不小于任何子节点的值。我们用
(1) 从以下选项中选择所有二叉堆树。

(2) 假设我们有一个高度为 2 的二叉树
(3) 假设我们有两个二叉堆树
(4) 假设我们有一个二叉树
(5) 展示一个算法,使用你在 (4) 中展示的操作按降序排列整数数组。展示该算法相对于数组中元素数量的最坏时间复杂度。
Kai
(1)
Choose all binary heap trees from the following.
A binary heap tree is a binary tree where the value of a parent node is no less than the value of any child node.
Let's analyze each tree:
- Tree (A) has only one node, so it is a binary heap tree.
- Tree (B) has a root node with value 5 and one child node also with value 5. This satisfies the binary heap property.
- Tree (C) has a root node with value 3, and two child nodes with values 1 and 4. Since
, this does not satisfy the binary heap property. - Tree (D) has a root node with value 9, child nodes with values 1 and 5. The node with value 5 has children with values 3 and 2. This satisfies the binary heap property.
Therefore, the binary heap trees from the given options are (A), (B), and (D).
(2)
Algorithm to make a binary tree
- Input: A binary tree
of height 2. - Output: A binary heap tree.
Algorithm:
- Let
be the root node. - Let
and be the children of . - Compare
with , then compare the larger child with . - If
is less than the larger child, exchange the labels of and the larger child.
This algorithm ensures that the tree satisfies the binary heap property by performing at most one exchange operation per child.
(3)
Algorithm to create a binary heap tree
- Input: Binary heap trees
and , root node . - Output: A binary heap tree
.
Algorithm:
- Create a new tree
with root node . - Set the left child of
as the root of and the right child of as the root of . - Perform a
heapify
operation on: - Compare
with its children. - If
is less than any of its children, exchange the labels of and the larger child. - Perform the same
heapify
operation on the child node that was exchanged.
- Compare
The worst-case time complexity of this algorithm is
(4)
Algorithm to make a binary tree
- Input: A binary tree
. - Output: A binary heap tree.
Algorithm:
- Start from the last non-leaf node and move upwards to the root node.
- For each node, perform the "heapify" operation:
- Compare the node with its children.
- If the node is less than any of its children, exchange the labels of the node and the larger child.
- Repeat the process until the root node is processed.
The worst-case time complexity of this algorithm is
(5)
Algorithm to sort in descending order an array of integers using the operations shown in (4):
- Input: An array of integers.
- Output: A sorted array in descending order.
Algorithm:
- Build a max-heap from the array using the algorithm from Question 4.
- Repeatedly extract the maximum element from the heap, replacing it with the last element of the heap, and place the maximum element at the end of the array.
- Perform heapify on the root node to restore the heap property.
Steps:
- Construct the max-heap:
- For each node starting from the last non-leaf node to the root, perform heapify.
- Sort the array:
- Swap the root of the heap with the last element of the heap.
- Reduce the heap size by one.
- Perform heapify on the root.
- Repeat until the heap size is 1.
The worst-case time complexity of this sorting algorithm is
Knowledge
堆 二叉堆 Heapify
难点思路
问题 (4) 的算法是关键,需要理解 heapify 操作以及其时间复杂度分析。
解题技巧和信息
- 构造二叉堆时,使用自底向上的
heapify
操作,确保每个子树都是一个堆。 - 在堆排序中,最大元素总是堆顶,通过交换堆顶和末尾元素并缩小堆大小,可以逐步将数组排序。
重点词汇
- Binary Heap 二叉堆
- Heapify 堆化
- Tree Height 树高
参考资料
- Introduction to Algorithms, Cormen et al., Chap. 6. Heapsort
- Data Structures and Algorithm Analysis in C, Mark Allen Weiss, Chap. 5. Priority Queues