专栏首页aCloudDeveloper算法导论第六章堆排序(一)

算法导论第六章堆排序(一)

现在来看, 堆的含义大概有两种,一种是数据结构,一种是在一些语言中所定义的“垃圾回收机制”,如Java,在书本上的开篇强调了这两者,并强调若非特殊说明,皆把堆看做是一种数据结构。

(二叉)堆的定义:

1)它是一个数组,可以被看成是一棵近似的完全二叉树,树上的每一个节点看做是数组中的每一个元素。

2)堆分为最大堆和最小堆,最大堆中每一棵子树的父节点的值大于孩子节点,最小堆则相反。

3)表示堆的数组A包括两个属性:A.length和A.heap_size。前者是数组元素的个数,后者是堆元素的个数,heap_size <= length。(怎么理解这里,想象一棵树的节点在减少,但其表示的数组的个数还是不变的)。

4)二叉堆是最常用的,除此之外,还有多叉堆,如习题6-2的d-叉堆。

5)已知一个节点的坐标,容易得到其父节点和孩子节点的坐标:PARENT(i) = i/2; LEFT(i) = 2*i; RIGHT(i)=2*i+1。

由于二叉堆可以看做是一棵完全二叉树,所以树的一些定理,结论可以应用到堆上,如高度为h的堆中元素个数最多为:2^h,最少为:2^(h+1) - 1; 含n个元素的堆高度为:lgn。

堆排序:

为了实现堆排序,需要有这样的几个过程:

1)Build_Max_Heap():建立最大堆,将无序的输入数组构造出一个最大堆;

2)Max_Heapify():维护一个最大堆,即保证满足最大堆的性质;

3)Heap_Sort():堆排序。

以上函数的思路也是比较简单,在此就不做过多记录,即便记录,也是照着书本上的流程来一遍。

首先,Max_Heapify()是一个很关键的函数,它要保证堆中元素在以后的操作过程中,不管怎么变,都要保证满足最大堆的性质,即父节点的值永远大于孩子节点,知道了这一点,就不难写出代码:

函数原型:Max_Heapify( int A[], /* int heap_size, */ int index )

 1 void MaxHeapify_Recur(int arr[], int heap_size, int index)
 2 {
 3     if (index <=0 && index >= heap_size)
 4         return;
 5 
 6     int left = LEFT(index);
 7     int right = RIGHT(index);
 8     int largest;
 9 
10     if (left < heap_size && arr[left] > arr[index])
11         largest = left;
12     else 
13         largest = index;
14 
15     if (right < heap_size && arr[right] > arr[largest])
16         largest = right;
17 
18     if (largest != index) {
19         Swap(arr[index], arr[largest]);
20         MaxHeapify_Recur(arr, heap_size, largest);
21     }
22 }

上面实现的是一个递归的版本,也是书本上的版本,同时习题6.2-5要求实现非递归的版本,其实改动很小,只需加入一个标识符即可,实现如下:

 1 void MaxHeapify(int arr[], int heap_size, int index)
 2 {
 3     if (index < 0 && index >= heap_size)
 4         return;
 5     
 6     bool isHeapify = true; //标识最大堆是否处理完
 7     while (isHeapify && index < heap_size) {
 8         int left = LEFT(index);
 9         int right = RIGHT(index);
10         int largest;
11 
12         if (left < heap_size && arr[left] > arr[index]) 
13             largest = left;
14         else 
15             largest = index;
16 
17         if (right < heap_size && arr[right] > arr[largest])
18             largest = right;
19 
20         if (largest != index) {
21             Swap(arr[index], arr[largest]);
22             index = largest;
23         }
24         else
25             isHeapify = false;
26     }
27 }

其次,Build_Max_Heap()的实现需要知道下面一条定理( 习题6.1-7 ) :

当用数组表示存储n个元素的堆时,叶节点下标分别是n/2+1, n/2+2, ..., n (结合树高度的性质,很好证明).

知道了这个定理,为了建立最大堆,我们就可以从第一个非叶子节点开始往后遍历,直到根节点,调用Max_Heapify()来得到一个最大堆,实现如下:

函数原型:Build_Max_Heap( int A[], /* int heap_size, */ )

1 void BuildMaxHeap(int arr[], int heap_size)
2 {
3     if (heap_size == 0)
4         return;
5     
6     for (int i = (heap_size-1)/2; i >= 0; i--)
7         MaxHeapify(arr, heap_size, i);
8 }

至此,排序思路也就出来了:先建立最大堆,得到最大元素,然后将最大元素放在数组末尾,然后调用Max_Heapify()维护最大堆,依次下去,就得到排序的数组,实现如下:

函数原型:Heap_Sort( int A[], /* int heap_size, */ )

 1 void HeapSort(int arr[], int length)
 2 {
 3     if (length == 0)
 4         return;
 5 
 6     int heap_size = length;
 7     BuildMaxHeap(arr, heap_size);
 8     for (int i = length-1; i >= 1; i --) {
 9         Swap(arr[0], arr[i]);
10         heap_size --;
11         MaxHeapify(arr, heap_size, 0);
12     }
13 }

堆排序的时间复杂度:

Max_Heapify()可以看到是在不断遍历树,最坏情况下是从根节点开始,则n个节点的树高为lgn,所以其时间复杂度为O(lgn)。

Build_Max_Heap()经过严格推导,可得时间复杂度为线性的,为O(n)。

所以,Heap_Sort()就为O(nlgn)。

同样的思路可以实现最小堆,下面贴出最大堆完整实现的代码:

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 
  6 //#include "HeapSort.h"
  7 
  8 #define PARENT(x) ((x-1)/2)    //求 x 父节点的下标
  9 #define LEFT(x) ((x)*2+1)    //求 x 左孩子的下标
 10 #define RIGHT(x) ((x)*2+2)    //求 x 右孩子的下标
 11 
 12 void MaxHeapify(int arr[], int heap_size, int index);        //维护最大堆的性质
 13 void MaxHeapify_Recur(int arr[], int heap_size, int index); //递归
 14 void BuildMaxHeap(int arr[], int heap_size);                    //从一个无序的数组中构造一个最大堆
 15 void HeapSort(int arr[], int length);                            //堆排序
 16 void Swap(int &a, int &b);
 17 
 18 void MaxHeapify(int arr[], int heap_size, int index)
 19 {
 20     if (index < 0 && index >= heap_size)
 21         return;
 22     
 23     bool isHeapify = true; //标识最大堆是否处理完
 24     while (isHeapify && index < heap_size) {
 25         int left = LEFT(index);
 26         int right = RIGHT(index);
 27         int largest;
 28 
 29         if (left < heap_size && arr[left] > arr[index]) 
 30             largest = left;
 31         else 
 32             largest = index;
 33 
 34         if (right < heap_size && arr[right] > arr[largest])
 35             largest = right;
 36 
 37         if (largest != index) {
 38             Swap(arr[index], arr[largest]);
 39             index = largest;
 40         }
 41         else
 42             isHeapify = false;
 43     }
 44 }
 45 
 46 void MaxHeapify_Recur(int arr[], int heap_size, int index)
 47 {
 48     if (index <=0 && index >= heap_size)
 49         return;
 50 
 51     int left = LEFT(index);
 52     int right = RIGHT(index);
 53     int largest;
 54 
 55     if (left < heap_size && arr[left] > arr[index])
 56         largest = left;
 57     else 
 58         largest = index;
 59 
 60     if (right < heap_size && arr[right] > arr[largest])
 61         largest = right;
 62 
 63     if (largest != index) {
 64         Swap(arr[index], arr[largest]);
 65         MaxHeapify_Recur(arr, heap_size, largest);
 66     }
 67 }
 68 
 69 void BuildMaxHeap(int arr[], int heap_size)
 70 {
 71     if (heap_size == 0)
 72         return;
 73     
 74     for (int i = (heap_size-1)/2; i >= 0; i--)
 75         MaxHeapify(arr, heap_size, i);
 76 }
 77 
 78 void HeapSort(int arr[], int length)
 79 {
 80     if (length == 0)
 81         return;
 82 
 83     int heap_size = length;
 84     BuildMaxHeap(arr, heap_size);
 85     for (int i = length-1; i >= 1; i --) {
 86         Swap(arr[0], arr[i]);
 87         heap_size --;
 88         MaxHeapify(arr, heap_size, 0);
 89     }
 90 }
 91 
 92 void Swap(int &a, int &b)
 93 {
 94     int temp = a;
 95     a = b;
 96     b = temp;
 97 }
 98 
 99 // int main()
100 // {
101 //     int arr[10] = {10,14,16,8,7,9,3,2,4,1};
102 //     HeapSort(arr, 10);
103 //     for (int i = 0; i < 10; i ++)
104 //         cout << arr[i] << " ";
105 //     return 0;
106 // }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论第六章优先队列(二)

    优先队列可以说是堆的一个非常重要的应用,和堆对应,优先队列也分最小优先队列和最大优先队列。 优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中每一个元...

    CloudDeveloper
  • 算法导论第七章快速排序

    一、快速排序概述 关于快速排序,我之前写过两篇文章,一篇是写VC库中的快排函数,另一篇是写了快排的三种实现方法。现在再一次看算法导论,发现对快速排序又有了些新的...

    CloudDeveloper
  • Linux探秘之用户态与内核态

    一、 Unix/Linux的体系架构 ?   如上图所示,从宏观上来看,Linux操作系统的体系架构分为用户态和内核态(或者用户空间和内核)。内核从本质上看是一...

    CloudDeveloper
  • 算法之常见排序算法-冒泡排序、归并排序、快速排序

    对于编程中琳琅满目的算法,本人向来是不善此道也不精于此的,而说起排序算法,也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时,面试官便让手写冒泡排序(入职...

    本人秃顶程序员
  • 数据结构之堆

    有没有更优的数据结构?使用堆,可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。

    崔笑颜
  • 执行对象Statement、PreparedStatement和CallableStatement详解 JDBC简介(五)

    执行对象是SQL的执行者,SQL是“安排好的任务”,执行对象就是“实际工作的人”。

    noteless
  • lodash源码分析之baseFindIndex中的运算符优先级

    我悟出权力本来就是不讲理的——蟑螂就是海米;也悟出要造反,内心必须强大到足以承受任何后果才行。 ——北岛《城门开》 本文为读 lodash 源码的第十篇,后...

    对角另一面
  • 漫画:什么是树状数组?

    我们学习数据结构的目的在于将我们的算法变得更快。由 Peter M. Fenwick 提出的树状数组 BIT 结构就是一个优秀的数据结构,BIT 全称 Bina...

    程序员小浩
  • 你所能用到的数据结构(四)

    五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

    一心一怿
  • lodash源码分析之baseFindIndex中的运算符优先级

    本文为读 lodash 源码的第十篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

    对角另一面

扫码关注云+社区

领取腾讯云代金券