東京大学 新領域創成科学研究科 メディカル情報生命専攻 2014年8月実施 問題9

Author

zephyr

Description

An array of real numbers, , is called a heap if for , where is the quotient of integer divided by 2 (e.g., ). A heap can be treated as a binary tree such that is the root node and is the parent node of . Answer the following questions.

(1) Explain whether array is a heap or not.

(2) Show that if is a heap, is also a heap for any .

(3) Suppose that is a heap but is not. Describe a procedure that exchanges elements in to make it a heap in worst-case time.

(4) Suppose that is a heap. Prove that is maximum among all elements in . Suppose that after replacing with , is not a heap. Describe a procedure that exchanges elements in to make it a heap in worst-case time.

(5) Describe an algorithm that exchanges elements in to make it a heap in worst-case time.

(6) Using the procedures defined above, describe an algorithm that sorts array in worst-case time.

---

一个包含 个实数的数组 ，如果满足 对于 ，其中 是整数 除以 2 的商（例如，），则称其为堆。堆可以被看作是一个二叉树，其中 是根节点， 是 的父节点。回答以下问题。

(1) 解释数组 是否是一个堆。

(2) 证明如果 是一个堆，那么 也是一个堆，对于任何 。

(3) 假设 是一个堆，但 不是。描述一种在 最坏情况下，将 中的元素交换使其成为堆的方法。

(4) 假设 是一个堆。证明 是 中最大的元素。假设在用 替换 后， 不是一个堆。描述一种在 最坏情况下，将 中的元素交换使其成为堆的方法。

(5) 描述一种在 最坏情况下，将 中的元素交换使其成为堆的算法。

(6) 使用上述定义的方法，描述一种在 最坏情况下，对数组 进行排序的算法。

Kai

(1)

To determine if the given array is a heap, we need to check if for every , the condition holds.

• :
• :
• :
• :
• :
• :
• :

Since is not greater than or equal to , the array is not a heap.

(2)

Statement: If is a heap, then is also a heap for any .

Proof: Let be a heap, meaning for all . Consider any . Since the heap property holds for all elements in , it will also hold for all elements in because the parent-child relationships in the heap are preserved up to index . Therefore, is also a heap.

(3)

Suppose is a heap, but after inserting an element at position , the array is not a heap. The violation of the heap property could only occur if the newly inserted element at position is greater than its parent. To fix this, we perform the heapify-up operation.

Heapify-up Procedure:

1. Let .
2. While and :
   • Swap and .
   • Set .

Time Complexity: The worst-case time complexity of this procedure is , as we may need to traverse up the height of the heap, which is logarithmic in terms of the number of elements.

(4)

Proof that is the maximum element in : By the definition of a max-heap, the root node (i.e., ) must be greater than or equal to all its children. By induction, it can be proven that is greater than or equal to all elements in the heap. Hence, is the maximum element.

Heapify-down Procedure: After replacing with , if is not a heap, we need to restore the heap property by performing the heapify-down operation.

1. Let .
2. While (i.e., while has at least one child):
   • Let (left child).
   • If and , set (right child is larger).
   • If , break the loop.
   • Swap and .
   • Set .

Time Complexity: The worst-case time complexity of this procedure is , as we may need to traverse down the height of the heap.

(5)

To convert an unordered array into a heap, we can use the build-heap algorithm:

Build-Heap Algorithm:

1. Start from the last non-leaf node, .
2. Perform heapify-down on each node from to 1.

Time Complexity: The build-heap process has a time complexity of , as it performs a linear number of operations over the array.

(6)

Using the above procedures, we can describe the Heapsort algorithm:

1. Build-Heap: Convert the array into a max-heap.
2. Extract-Max repeatedly: Swap with , reduce the size of the heap by 1, and then perform heapify-down on .
3. Repeat the above step until the heap size is reduced to 1.

Time Complexity: The time complexity of Heapsort is because:

• Building the heap takes time.
• Each extraction and heapify-down takes time, and there are such extractions.

Knowledge

堆 堆排序 复杂度分析

解题技巧和信息

堆问题的核心是维护堆的性质，通过理解堆的定义（最大堆或最小堆）来选择合适的操作（如 heapify-up 或 heapify-down）。在建堆和堆排序时，关注堆的高度和操作的时间复杂度。堆操作通常具有 的时间复杂度，而建堆的复杂度为 。

重点词汇

• heap 堆
• heapify 堆化
• max-heap 最大堆
• build-heap 建堆
• heapify-down 下滤
• heapify-up 上滤

参考资料

1. Introduction to Algorithms, 3rd Edition, Chapter 6: Heapsort
2. Data Structures and Algorithm Analysis in C, Chapter 7: Heaps