算法系列： 10大常见排序算法: 堆排序（1）堆的数据结构

一句

 堆就是用数组实现的二叉树,特省空间

把二叉树存放在数组里

这是一个二叉树，想一下如何把这个二叉树存在数组里？

当然，父节点和子节点的关系也需要保存下来。换句话说，存储在数组中的数据可以再还原出原来的二叉树。

很简单，从最上面一层开始，按顺序放到数组里：

这个二叉树从最顶端的第0层开始，一共有4层。我们来看一下每一层有多少个节点，然后找到每一层第一个节点在数组里的下标值。

第0层的节点数： 2^0 = 1

第1层的节点数： 2^1 = 2

第2层的节点数： 2^2 = 4

第3层的节点数： 2^3 = 8

嗯，都是2的次方数

那么每一层的第一个节点在数组里的位置是前面所有节点数+1， 因为数组的索引是从0开始的，那么在数组中的索引位置需要减1:

第0层的第一个节点索引位置： 0

第1层的第一个节点索引位置： 2^0 + 1 - 1 = 2^0 = 2^1-1

第2层的第一个节点索引位置： 2^0+2^1 +1-1= 2^0+2^1= 2^2-1

第3层的第一个节点索引位置：  2^0+2^1 + 2^2 + 1-1= 2^0+2^1 + 2^2 = 2^3-1

规律是： 第n层的第一个节点是索引位置 = 2^n -1     (n = 0,1,2...)

问题：

答案：

因为第n层的第一个节点是2^n -1, 所以x在第n层。

下面来推导计算第几层的简单公式：

堆中父节点和子节点的索引变换

如果 i 是节点的索引， 下面我们来找到它的父节点和子节点在数组中的位置

left(i)  表示二叉树中i的左子节点索引位置

right(i)  表示二叉树中i的右子节点索引位置

parent(i) 表示二叉树中i的父节点索引位置

我们来看一下节点i的同一层第一个节点的子节点。这里i是5，同层第一个节点是3.

节点3的左子节点是7, 也是下一层的第一个节点。 现在来使用每层第一个节点的计算公式： 2^n - 1   

也就是左子节点 = 【该节点索引值】 乘以【2】 加  【1】

现在从本层的第一个节点3移动到节点j (5). 我们注意到：当我们在同一层中向右移动节点时（3到5），因为每个节点有左右2个子节点，相应的子节点索引值以2倍的距离移动（7到11）。 

上图显示子节点层的移动距离是父节点层的2倍

也就是对于一个节点（5），对于它的左子节点的索引值依然是 2倍的值加1.

：总结一下：

一句

这是堆中父节点和子节点索引的换算公式