引用
2.jpg
信息：
堆是采用从左到右进行填充的。如果我们知道了父节点为i，那么左孩子节点为2i，右孩子节点为2i+1。
大根堆和小根堆
大根堆特点：A[parent(i)] >= A[i]
小根堆特点：A[parent(i)] <= A[i]
构造堆结构
思想：
如果我们要构造大根堆，我们可以把每一个堆节点看做一个完整的堆结构，遍历每一个堆节点，然后将每一个堆节点构成的堆结构保持父节点大于孩子节点即可。我们可以从下到上调整，注意叶子节点是没有孩子节点的。
代码：
//调整堆结构
public static void adjustDownHeap(int[] arr, int index) {
//缓存当前调整的节点
arr[0] = arr[index];
//将当前节点的左孩子节点作为最大节点
int maxSonIndex = 2*index;
while (maxSonIndex <= arr.length-1) {
//比较左孩子节点和右孩子谁最大，
if (maxSonIndex < arr.length-1 && arr[maxSonIndex] < arr[maxSonIndex+1]) {
maxSonIndex++;
}
//比较孩子节点和父亲节点谁最大
if (arr[maxSonIndex] > arr[0]) {
arr[maxSonIndex/2] = arr[maxSonIndex];
} else {
break;
}
maxSonIndex = maxSonIndex * 2;
}
arr[maxSonIndex/2] = arr[0];
}
//遍历堆中拥有孩子的节点
public static void createHeap(int[] inArr) {
for (int i = inArr.length/2 ; i > 0 ; i--) {
adjustDownHeap(inArr, i);
}
}
测试：
public static void printArr(int[] objArr) {
for (int i : objArr) {
System.out.println(i);
}
}
public static void main(String[] args) {
int[] arr ={1,2,3,4,5,6,7,8};
int[] inArr = new int[arr.length+1];
for (int i = 0 ; i < arr.length ; i++) {
inArr[i+1] = arr[i];
}
createHeap(inArr);
printArr(inArr);
}
结果：
3.jpg
