Cormen 的零索引最大堆化算法
我正在尝试实现算法书中给出的最大堆算法此处 书中的算法是
MAX-HEAPIFY(A,i)
1 l<-LEFT(i)
2 r<-RIGHT(i)
3 if l<=heap-size[A] and A[l]>A[i]
4 then largest<--l
5 else largest<--i
6 if r<=heap-size[A] and A[r]>A[largest]
7 then largest <->r
8 if largest!=i
9 then exchange A[i]<->A[largest]
10 MAX-HEAPIFY(A,largest)
我的问题是我的数组从零开始。正如在书中他们假设如果父级的索引是 i 那么左子级是 2i ，右子级是 2i+1 但那是他们的索引从 1 开始的时候。就我而言，它为零，那么我应该如何计算左右孩子的索引呢？
I am trying to implement max heapify algorithm given in Algorithms Book here
The algo in book is
MAX-HEAPIFY(A,i)
1 l<-LEFT(i)
2 r<-RIGHT(i)
3 if l<=heap-size[A] and A[l]>A[i]
4 then largest<--l
5 else largest<--i
6 if r<=heap-size[A] and A[r]>A[largest]
7 then largest <->r
8 if largest!=i
9 then exchange A[i]<->A[largest]
10 MAX-HEAPIFY(A,largest)
My problem is my array is starting at Zero.Where as in book they assumed that if index of parent is i then left child is 2i and right child is 2i+1 but that is when their indices start from 1.In my case it is zero so what how should I calculate index of left and right child?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
左子节点位于 2i+1，右子节点位于 2(i+1) = 2i+2。
来证明这是正确的
您可以通过调用基于一的索引 j、定义 i = j - 1 并观察它
（您还可以通过过度分配单个元素来省去一些麻烦。）
The left child is at 2i+1, the right child is at 2(i+1) = 2i+2.
You can prove that this is correct by calling your one-based indices j, defining i = j - 1 and observing that
so
(You can also save yourself some trouble by overallocating a single element.)