构建二叉堆

二叉堆本身也是个二叉树，有两个限制：

堆必须是完全二叉树堆中任一父结点的值大于其左右两子节点的值（大顶堆），或小于其左右两子节点的值（小顶堆）

因为完全二叉树中，数据排列顺序是从上而下，从左至右，所以可以用数组的形式保存数据。通常根结点作为数组的 0 号元素，其左右孩子分别是 2 号、3 号元素，以此类推。

保证一个元素符合要求

保证一个元素符合要求的过程，可以叫做 heapify。其顺序是：

如果元素超限，退出比较元素值及其左右孩子结点的值（前提是有），如果元素值是最大的则无需交换，否则跟最大值交换回到第一步，递归比较元素的左右两个孩子 void swap(int tree[], int i, int j) { int tmp = tree[i]; tree[i] = tree[j]; tree[j] = tmp; } void heapify(int tree[], int n, int i) { if (i >= n) { return; } int max = i; int c1 = i * 2 + 1; int c2 = i * 2 + 2; if (c1 < n && tree[i] < tree[c1]) { max = c1; } if (c2 < n && tree[max] < tree[c2]) { max = c2; } if (max != i) { swap(tree, i, max); } heapify(tree, n, c1); heapify(tree, n, c2); }

保证整个二叉树符合要求

每次 heapify 可以确保二叉树中的最大元素上移一层，所以需要对除最后一层外的所有元素逐个调用 heapify：

void heapifyAll(int tree[], int n) { int last = (n - 1) / 2; int i; for (i = last; i >= 0; i--) { heapify(tree, n, i); } }

排序

二叉堆构建完成后，就可以对其进行排序了。步骤如下：

交换根结点和最后一个结点结点个数减一，然后重新对根结点进行 heapify继续第一、二步，直到没有结点为止 void heapSort(int tree[], int n) { heapifyAll(tree, n); int i; for (i = n - 1; i >= 0; i--) { swap(tree, 0, i); heapify(tree, i, 0); } }

完整代码：

#include <stdio.h> void swap(int tree[], int i, int j) { int tmp = tree[i]; tree[i] = tree[j]; tree[j] = tmp; } // 对单个结点堆化 void heapify(int tree[], int n, int i) { if (i >= n) { return; } int max = i; int c1 = i * 2 + 1; int c2 = i * 2 + 2; if (c1 < n && tree[i] < tree[c1]) { max = c1; } if (c2 < n && tree[max] < tree[c2]) { max = c2; } if (max != i) { swap(tree, i, max); } heapify(tree, n, c1); heapify(tree, n, c2); } // 对整个完全二叉树堆化 void heapifyAll(int tree[], int n) { int last = (n - 1) / 2; int i; for (i = last; i >= 0; i--) { heapify(tree, n, i); } } // 堆排序 void heapSort(int tree[], int n) { heapifyAll(tree, n); int i; for (i = n - 1; i >= 0; i--) { swap(tree, 0, i); heapify(tree, i, 0); } } int main(void) { int i; int tree[6] = {3, 2, 5, 4, 7, 1}; // heapify(tree, 6, 1); heapifyAll(tree, 6); printf("堆：\n"); for( i = 0; i < 6; i++) { printf("%d\n", tree[i]); } heapSort(tree, 6); printf("新顺序：\n"); for( i = 0; i < 6; i++) { printf("%d\n", tree[i]); } return 0; }

转载于:https://www.cnblogs.com/kika/p/10851498.html