C语言实现基于最大堆和最小堆的堆排序算法示例

堆定义
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小顶堆）或者：Key[i]>=Key[2i+1]&&key>=key[2i+2]（大顶堆）
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

• 最大堆：所有节点的子节点比其自身小的堆。
• 最小堆：所有节点的子节点比其自身大的堆。

这里以最大堆为基础，其基本思想为：

1.将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

C语言实现
1.基于最大堆实现升序排序

// 初始化堆
void initHeap(int a[], int len) {
 // 从完全二叉树最后一个非子节点开始
 // 在数组中第一个元素的索引是0
 // 第n个元素的左孩子为2n+1，右孩子为2n+2，
 // 最后一个非子节点位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMaxHeap(a, len, i);
 }
}

void adjustMaxHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一个元素，那么只能是堆顶元素，也没有必要再排序了
 if (len <= 1) {
  return;
 }

 // 记录比父节点大的左孩子或者右孩子的索引
 int targetIndex = -1;

 // 获取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;

 // 没有左孩子
 if (leftChildIndex >= len) {
  return;
 }

 // 有左孩子，但是没有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子两者中最大的一个
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }

 // 只有孩子比父节点的值还要大，才需要交换
 if (a[targetIndex] > a[parentNodeIndex]) {
  int temp = a[targetIndex];

  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;

  // 交换完成后，有可能会导致a[targetIndex]结点所形成的子树不满足堆的条件，
  // 若不满足堆的条件，则调整之使之也成为堆
  adjustMaxHeap(a, len, targetIndex);
 }
}

void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }

 // 初始堆成无序最大堆
 initHeap(a, len);

 for (int i = len - 1; i > 0; --i) {
  // 将当前堆顶元素与最后一个元素交换，保证这一趟所查找到的堆顶元素与最后一个元素交换
  // 注意：这里所说的最后不是a[len - 1]，而是每一趟的范围中最后一个元素
  // 为什么要加上>0判断？每次不是说堆顶一定是最大值吗？没错，每一趟调整后，堆顶是最大值的
  // 但是，由于len的范围不断地缩小，导致某些特殊的序列出现异常
  // 比如说，5, 3, 8, 6, 4序列，当调整i=1时，已经调整为3,4,5,6,8序列，已经有序了
  // 但是导致了a[i]与a[0]交换，由于变成了4,3,5,6,8反而变成无序了!
  if (a[0] > a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }

  // 范围变成为：
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 结束
  // 其中，0是堆顶，每次都是找出在指定的范围内比堆顶还大的元素，然后与堆顶元素交换
  adjustMaxHeap(a, i - 1, 0);
 }
}

2.基于最小堆实现降序排序

// 初始化堆
void initHeap(int a[], int len) {
 // 从完全二叉树最后一个非子节点开始
 // 在数组中第一个元素的索引是0
 // 第n个元素的左孩子为2n+1，右孩子为2n+2，
 // 最后一个非子节点位置在(n - 1) / 2
 for (int i = (len - 1) / 2; i >= 0; --i) {
  adjustMinHeap(a, len, i);
 }
}

void adjustMinHeap(int a[], int len, int parentNodeIndex) {
 // 若只有一个元素，那么只能是堆顶元素，也没有必要再排序了
 if (len <= 1) {
  return;
 }

 // 记录比父节点大的左孩子或者右孩子的索引
 int targetIndex = -1;

 // 获取左、右孩子的索引
 int leftChildIndex = 2 * parentNodeIndex + 1;
 int rightChildIndex = 2 * parentNodeIndex + 2;

 // 没有左孩子
 if (leftChildIndex >= len) {
  return;
 }

 // 有左孩子，但是没有右孩子
 if (rightChildIndex >= len) {
  targetIndex = leftChildIndex;
 }
 // 有左孩子和右孩子
 else {
  // 取左、右孩子两者中最上的一个
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex;
 }

 // 只有孩子比父节点的值还要小，才需要交换
 if (a[targetIndex] < a[parentNodeIndex]) {
  int temp = a[targetIndex];

  a[targetIndex] = a[parentNodeIndex];
  a[parentNodeIndex] = temp;

  // 交换完成后，有可能会导致a[targetIndex]结点所形成的子树不满足堆的条件，
  // 若不满足堆的条件，则调整之使之也成为堆
  adjustMinHeap(a, len, targetIndex);
 }
}

void heapSort(int a[], int len) {
 if (len <= 1) {
  return;
 }

 // 初始堆成无序最小堆
 initHeap(a, len);

 for (int i = len - 1; i > 0; --i) {
  // 将当前堆顶元素与最后一个元素交换，保证这一趟所查找到的堆顶元素与最后一个元素交换
  // 注意：这里所说的最后不是a[len - 1]，而是每一趟的范围中最后一个元素
  // 为什么要加上>0判断？每次不是说堆顶一定是最小值吗？没错，每一趟调整后，堆顶是最小值的
  // 但是，由于len的范围不断地缩小，导致某些特殊的序列出现异常
  // 比如说，5, 3, 8, 6, 4序列，当调整i=1时，已经调整为3,4,5,6,8序列，已经有序了
  // 但是导致了a[i]与a[0]交换，由于变成了4,3,5,6,8反而变成无序了!
  if (a[0] < a[i]) {
   int temp = a[0];
   a[0] = a[i];
   a[i] = temp;
  }

  // 范围变成为：
  // 0...len-1
  // 0...len-1-1
  // 0...1 // 结束
  // 其中，0是堆顶，每次都是找出在指定的范围内比堆顶还小的元素，然后与堆顶元素交换
  adjustMinHeap(a, i - 1, 0);
 }
}

3.C语言版测试

大家可以测试一下：

// int a[] = {5, 3, 8, 6, 4};
int a[] = {89,-7,999,-89,7,0,-888,7,-7};
heapSort(a, sizeof(a) / sizeof(int));

for (int i = 0; i < sizeof(a) / sizeof(int); ++i) {
  NSLog(@"%d", a[i]);
}