服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 解读堆排序算法及用C++实现基于最大堆的堆排序示例

解读堆排序算法及用C++实现基于最大堆的堆排序示例

2021-04-06 13:26C++教程网 C/C++

把待排序的数组构造出最大堆是进行堆排序操作的基本方法,这里将带大家来解读堆排序算法及用C++实现基于最大堆的堆排序示例,首先从堆排序的概念开始:

1、堆排序定义
n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如最小堆示例和最大堆示例所示。
堆排序算法

解读堆排序算法及用C++实现基于最大堆的堆排序示例

 

2、最大堆和最小堆
(1)根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为最小堆。
(2)结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为最大堆。
注意:
(1)堆中任一子树亦是堆。
(2)以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

3、堆排序的基本思路如下:
(1)把待排序数组构造成一个最大堆
(2)取出树的根(最大(小)值, 实际算法的实现并不是真正的取出)
(3)将树中剩下的元素再构造成一个最大堆(这里的构造和第1步不一样,具体看实现部分)
(4)重复2,3操作,直到取完所有的元素
(5)把元素按取出的顺序排列,即得到一个有序数组(在代码实现里是通过交换操作"无形中"完成的)
在开始实现算法先看几个结论(证明略):
(1)完全二叉树A[0:n-1]中的任意节点,其下标为 ii, 那么其子节点的下标分别是为2i+12i+1 和 2(i+1)2(i+1)
(2)大小为n的完全二叉树A[0:n-1],叶子节点中下标最小的是⌊n2⌋⌊n2⌋, 非叶子节点中下标最大的是⌊n2⌋−1⌊n2⌋−1
(3)如果数组是一个最大堆,那么最大元素就是A[0]
(4)最大堆中任意节点的左右子树也是最大堆
 
4、实现示例
这里的算法实现使用的是最大堆,首先来解决由数组建立最大堆的问题:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 用于计算下标为i的节点的两个子节点的下标值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
         
/* 此函数把一颗二叉树中以node为根的子树变成最大堆。
 * 注意: 使用的前提条件是 node节点的左右子树(如果存在的话)都是最大堆。
 * 这个函数是整个算法的关键。
 */
void max_heapify(int heap[], int heap_size, int node)
{
  // 这里先不考虑整数溢出的问题
  // 先把注意力放在主要的功能上
  // 如果数据规模够大,int类型必然会溢出
  int l_child = LEFT(node);
  int r_child = RIGHT(node);
  int max_value = node;
 
  if (l_child < heap_size && heap[l_child] > heap[max_value])
  {
    max_value = l_child;
  }
  if (r_child < heap_size && heap[r_child] > heap[max_value])
  {
    max_value = r_child;
  }
  if (max_value != node)
  {
    swap_val(heap + node, heap + max_value);
 
    // 之后还要保证被交换的子节点构成的子树仍然是最大堆
    // 如果不是这个节点会继续"下沉",直到合适的位置
    max_heapify(heap, heap_size, max_value);
  }
}
 
/* 将一个数组构造成最大堆
 * 自底向上的利用max_heapify函数处理
 */
void build_max_heap(int heap[], int heap_size)
{
  if (heap_size < 2)
  {
    return;
  }
  int first_leaf = heap_size >> 1;//第一个叶子节点的下标
 
  int i;
  // 从最后一个非叶子节点开始自底向上构建,
  // 叶子节点都看作最大堆,因此可以使用max_heapify函数
  for (i = first_leaf - 1; i >= 0; i--)
  {
    max_heapify(heap, heap_size, i);
  }
}

函数max_heapify将指定子树的根节点"下沉"到合适的位置, 最终子树变成最大堆, 该过程最坏时间复杂度为O(logn)O(log⁡n)。函数build_max_heap自底向上的调用max_heapify, 最终整个数组满足最大堆,迭代过程的复杂度为O(nlogn)O(nlog⁡n), 因此整个函数的最坏时间复杂度也是O(nlogn)O(nlog⁡n)。 而如果当前数组已经是最大堆了,例如数组原本是降序排列的, 那么max_heapify过程的时间复杂度就是O(1)O(1), 此时build_max_heap的时间复杂度是O(n)O(n),这是最好的情况。

接着实现堆排序过程:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* heap sort 主函数
 */
void heap_sort(int heap[], int heap_size)
{
  if (heap == NULL || heap_size < 2)
  {
    return;
  }
  //构建最大堆
  build_max_heap(heap, heap_size);
 
  int i;
  for (i = heap_size - 1; i > 0; i--)
  {
    /* 把当前树的根节点交换到末尾
     * 相当于取出最大值,树的规模变小。
     * 交换后的树不是最大堆,但是根的两颗子树依然是最大堆
     * 满足调用max_heapify的条件。之所以这样交换,
     * 是因为用max_heapify处理时间复杂度较低,
     * 如果不交换而直接"取出"heap[0], 此处可能要使用
     * build_max_heap重新建立最大堆,时间复杂度较大
     */
    swap_val(heap, heap + i);
 
    heap_size--;
    //维护最大堆
    max_heapify(heap, heap_size, 0);
  }
}

最终的堆排序算法中,build_max_heap的复杂度是已知的, 迭代部分和build_max_heap的实现类似,而且不难看出, 交换后的根元素在下一次建堆过程中必然下沉到堆底,因此无论情况好坏, 该迭代过程时间复杂度都是O(nlogn)O(nlog⁡n), 所以整个算法的最好最坏和平均时间复杂度都是O(nlogn)O(nlog⁡n)。
堆排序算法的空间复杂度是O(1)O(1),从实现上很容易看出来。

延伸 · 阅读

精彩推荐