Problem 2679 --Heaps - Complete Binary Tree

2679: Heaps - Complete Binary Tree

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

Description

Complete Binary Tree

A complete binary tree is a binary tree in which every internal node has two children and all leaves have the same depth. A binary tree in which if last level is not completely filled but all nodes (leaves) are pushed across to the left, is also (nearly) a complete binary tree.

A binary heap data structure is an array that can be viewed as a nearly complete binary tree as shown in the following figure.

Each node of a nearly complete binary tree corresponds to an element of the array that stores the value in the node. An array A that represents a binary heap has the heap size H, the number of elements in the heap, and each element of the binary heap is stored into A[1...H] respectively. The root of the tree is A[1], and given the index ii of a node, the indices of its parent parent(i), left child left(i), right child right(i) can be computed simply by ⌊i/2⌋, 2×i and 2×i+1respectively. 

Write a program which reads a binary heap represented by a nearly complete binary tree, and prints properties of nodes of the binary heap in the following format: 

node id: key = k, parent key = pk, left key = lk, right key = rk,

id, k, pk, lk and rk represent id (index) of the node, value of the node, value of its parent, value of its left child and value of its right child respectively. Print these properties in this order. If there are no appropriate nodes, print nothing.

Input

In the first line, an integer H, the size of the binary heap, is given. In the second line, H integers which correspond to values assigned to nodes of the binary heap are given in order of node id (from 1 to H).

Output

Print the properties of the binary heap in the above format from node 1 to H in order. Note that, the last character of each line is a single space character.

Sample Input复制

5
7 8 1 2 3

Sample Output复制

node 1: key = 7, left key = 8, right key = 1, 
node 2: key = 8, parent key = 7, left key = 2, right key = 3, 
node 3: key = 1, parent key = 7, 
node 4: key = 2, parent key = 8, 
node 5: key = 3, parent key = 8,

提示

H≤250 

−2,000,000,000≤ value of a node ≤2,000,000,000

推荐代码 查看2679 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$26 $ms] 忆一九 808246 2022-02-02 15:32:13
内存最少[$41148 $KB] 忆一九 808246 2022-02-02 15:32:13
第一AC 忆一九 808246 2022-02-02 15:32:13
第一挑战 忆一九 808246 2022-02-02 15:32:13

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛