【完全二叉树魔法：顺序结构实现堆的奇象】（上）：https://developer.aliyun.com/article/1424931
4.堆的调整算法
4.1堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
//向下调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; //parent到叶子结点就结束 while (child < n) { //可能不存在右孩子 if (child + 1 < n && a[child] > a[child + 1]) { child++; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
4.2堆向上调整算法
现在我们给出一个数组，前n-1个数已经是堆了，现在再添加一个数要让其满足堆的性质。我们通过从最后一个叶子结点向上调整算法可以把它调整成一个小堆。向上调整算法有一个前提：前面的数据必须是一个堆，才能调整。
//向上调整 void AdjustUp(int* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
5.堆的创建
方法一：向上调整插入的思想
下面我们给出一个数组，利用上面push函数的思路，将数组a中的元素依次插入向上调整，把第一个数当成堆，满足堆向上调整的前提，可以调整成堆。
int a[] = {1,5,3,2,8};
//建堆 //向上调整：前提是前面的数据是堆 // 思路：第一个数据当作堆，后面数据依次插入，向上调整 //时间复杂度O(N*logN) for (int i = 1; i < n; i++) { AdjustUp(a, i); }
所以这里我们就可以给堆结合实现一个创建堆的接口：使用向上调整的思路。
void HeapInitArray(HP* php, int* a, int n) { assert(php); assert(a); php->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (php->a == NULL) { perror("malloc fail"); exit(-1); } php->size = php->capacity = n; memcpy(php->a, a, sizeof(HPDataType) * n); for (int i = 0; i < n; i++) { AdjustUp(php->a, i); } }
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：建堆的时间复杂度为O(N*logN)。
方法二：倒数第一个非叶子结点向下调整的思想
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。如果根节点左右子树是堆，我们可以直接向下调整即可，但是此时根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树与其叶子结点开始向下调整，调整完直接下标减一就是倒数的第二个非叶子节点，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6}; //倒数第一个非叶子结点:(最后一个叶子结点-1)/2
//建堆 //向下调整建堆 //找到倒数第一个非叶子结点 //时间复杂度O(N) for (int i = (n - 1 - 1)/2; i >= 0; i--) { AdjustDown(a, n, i); }
【完全二叉树魔法：顺序结构实现堆的奇象】（下）：https://developer.aliyun.com/article/1424935
