堆的下沉终止条件问题

来源：8-4 从堆中取出元素和Sift Down

慕少7158242

2018-09-25

老师你好，堆的siftdown的终止条件while(leftChild(k) < data.getSize())我实在没懂，如果此时索引为k的节点不是叶子节点，那他就会有叶子节点，而所有节点的的索引不都是小于等于data.size吗？麻烦你给我讲讲你这终止条件是个啥逻辑，谢谢！

写回答

1回答

liuyubobobo

2018-09-25

在我们的leftChild方法中，没有判断k是否存在左孩子节点，其实只是返回2*k+1而已。所以这个判断条件的意思是，如果k的左孩子节点的索引2*k+1 >= data.size()的话，说明k已经是叶子节点了（因为他的左孩子节点越界了），说明我们已经来到了整棵完全二叉树的底部：）

加油！：）

liuyubobobo

ciphermagic

谢谢，你是对的：）

2018-11-12

共4条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 2

回答 1

回答 1

回答 1