完全二叉树的顺序存储
R[1]存储二叉树的根结点。结点R[i]的左孩子（若有的话）存放在R[2i]处，而R[i]的右孩子（若有的话）存放在R[2i+1]处。R[i]的父结点是R[i/2]。
堆的上浮操作
当大根堆的元素值R[i]变大时，该结点可能会上浮。
（1）将R[i]与其父结点R[i/2]比较；
（2）若R[i]<=R[i/2]，则已满足堆序性，算法结束；
（3）否则交换R[i]和R[i/2]，令i上行指向其父亲i<--i/2，执行（1）.
/*堆的上浮操作*/
void ShiftUp(int R[], int n, int i) {//堆元素R[i]上浮，数组R[]存储堆，n为对包含的元素个数while (i > 1 && R[i] > R[i / 2]) { //R[i]比父亲大且i不是根（i!=1）swap(R[i], R[i / 2]); //交换R[i]和父亲i /= 2; //结点i继续上浮}
}堆的下沉操作
当大根堆的元素值R[i]变小时，该结点可能会下沉。
（1）将R[i]与其最大的孩子R[maxchd]比较；
（2）若R[i]>=R[maxchd]，则已满足堆序性，算法结束；
（3）否则交换R[i]和R[maxchd]，令i下行i<--maxchd，返回（1）
/*堆的下沉操作*/
void ShiftDown(int R[], int n, int i) {//堆元素R[i]下沉，数组R[]存储堆，n为堆包含的元素个数while (i <= n / 2) { //i最多下行至最后一个非叶结点int maxchd = 2 * i; //假定最大孩子为左孩子if (maxchd + 1 < n && R[maxchd] < R[maxchd + 1]) //maxchd+1<n保证i有右孩子；且i的右孩子比左孩子大maxchd++; //i的右孩子是最大孩子if (R[i] >= R[maxchd]) return;swap(R[maxchd], R[i]); //R[i]的最大孩子比R[i]大i = maxchd; //结点i继续下沉}
}初始建堆
从最后一个非叶结点开始，依次建立每个非叶结点为根的子堆。
从最后一个非叶结点开始，依次下沉结点n/2,n/2-1,...,1.
/*初始建堆*/
void BuildHeap(int R[], int n) {for (int i = n / 2; i >= 1; i--) {ShiftDown(R, n, i); //建立以i为根的堆，即下沉i}
}堆排序算法思想
（1）将待排序数组R建成一个大根堆；
（2）在前n个元素的堆里选最大元素R[1]，与R[n]交换使R[n]就位，下沉根结点R[1]使R[1]...R[n-1]重建为堆。
（3）在前n-1个元素的堆里选最大元素R[1]，与R[n-1]交换使R[n-1]就位，下沉根结点R[1]使R[1]...R[n-2]重建为堆。
（4）在前n-2个元素的堆里选最大元素R[1]，与R[n-2]交换使R[n-2]就位，下沉根结点R[1]使R[1]...R[n-3]重建为堆。
······
上述操作反复进行，知道调整范围只剩下一个元素R[1]为止。
此时，R[1]是n个元素中最小的，且数组R已按递增排列。
堆排序算法
/*堆排序算法*/
void HeapSort(int R[], int n) { //堆排序R[1]...R[n]BuildHeap(R, n); //将R建为堆for (int i = n; i > 1; i--) { //i为当前堆的堆尾swap(R[1], R[i]); //前i个元素的最大者R[1]与R[i]交换ShiftDown(R, i - 1, 1); //下沉R[1]使R[1]...R[i-1]重建为堆}
}