当前位置: 首页 > 编程笔记 >

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

公孙国兴
2023-03-14
本文向大家介绍C语言实现基于最大堆和最小堆的堆排序算法示例,包括了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]);
}
 类似资料:
  • 我只是想看看我是否理解教授和在线资源所说的话。 对于heapSort算法,第一个元素的索引从0开始。 对于最大堆,如果子堆大于父堆,则percolate down应将最大子堆与其父堆交换,例如(这是用于赋值,因此我尝试发布尽可能少的代码): 所以最后,最大元素应该在索引0处。 如果这是正确的,我不理解的是heapSort实现: 最大堆中的渗滤层不应该将最大的元素放在索引0处吗?在这种情况下,为什么

  • 我在[17,98,89,42,67,54,89,25,38]中有一个数字列表,从左到右插入到一个空堆中。生成的堆是什么?

  • 对于堆排序,如果我们想按升序对数组排序,那么应该在最大堆还是最小堆中转换堆?

  • 问题内容: 您是否知道一个流行的库(Apache,Google等),该库具有可靠的最小- 最大堆Java实现,即允许在其中查看其最小值和最大值并删除其中的元素的堆? 问题答案: 番石榴:。

  • 我注意到一件非常奇怪的事情。 读完这节课后,我在C中实现了一些堆排序代码。 代码如下。 奇怪的是,对我来说,构建min堆-提取min(或在构建min堆后在根目录下执行min-heapify)应该按升序进行。然而,在执行此代码并打印出结果向量后,我得到: 在试图弄清楚发生了什么的时候,我改变了 到 最终选择较大(或最大)的父节点和子节点,得到的向量为: 我是否做错了什么,或者我对堆/堆排序的理解不清

  • 我试过下面的程序。创建此程序的目的是了解有关堆栈大小的更多信息。 执行上述代码后,由于堆栈大小分配过大,程序崩溃。堆栈的最大可能大小是多少?是否为每个程序/计算机固定?可以增加吗? 我想知道是为了知识。如果有人能提供C/C中的例子,那将是非常有帮助的。