首页 > 编程语言 > 详细

堆排序

时间:2019-06-17 23:38:02      阅读:132      评论:0      收藏:0      [点我收藏+]

     最近在看极客时间的《数据结构与算法之美》专栏,边学边忘(记性实在是太差了),学习完后为了加深理解和便于后续复习,在博客上做笔记记录一下吧。

     堆排序主要有两个过程:建堆排序,这两个操作的关键思想都是堆化堆化即将一系列数据组织成大/小顶堆的过程,可以选择从上往下堆化(即从第一个非叶子节点开始,和其左右子树进行比较),也可以从下往上堆化(即将要操作的节点当作新节点,相当于往堆中插入新的节点,然后和其父节点比较),在这里我选择从上往下堆化,自己画图理解会好点。
  主要的点:当前节点K,在数组中从下标0开始存储数据,那么其父节点(K-1)/2,左子节点2*K+1,右子节点2*K+2,第一个非叶子节点K/2-1

  代码实现分析:(假设构建的是大顶堆,排序结果为升序)

  堆化:拿到第一个非叶子节点,和它的左右子树分别比较,如果左子树或者右子树的值比当前节点大,那么将当前节点与左右子树中的最大值交换,然后更新当前处理节点的下标为左子树/右子树的下标值,然后直到当前节点堆化完成,接下来处理第二个非叶子节点,处理步骤相同,一个节点一个节点的处理,直到处理完根节点,建堆完成。

  排序:构建的是大顶堆,那么根据定义,其堆顶必然为整个数据中的最大值,那么可以将其与堆尾元素交换,然后去除堆尾元素(最大值),这里的去除指的是将数组的最大值下标往前移动一位,因为最大值已经就位,接下来无需再处理。然后将去除堆尾元素的数据进行堆化,再次得到第二大值,同理,将其与堆尾交换,然后移动数组下标,堆化剩下的元素,直到堆中只有一个元素,至此,排序完成。

  其实堆排序的重点还是堆化,无论是初始化建堆,还是排序的过程,堆化是其实现的重点,排序的过程其实也是不断调用堆化操作的过程。

       代码实现如下:

 1 class HeapSort {
 2 public:
 3     int* heapSort(int* A, int n) {
 4         // write code here
 5         buildHeap(A, n);
 6         //排序
 7         for (int i = n - 1; i > 0; --i)
 8         {
 9             swap(A, 0, i);
10             heapfiy(A, i - 1, 0);
11         }
12         return A;
13     }
14     
15     //建堆
16     void buildHeap(int* A, int n)
17     {
18         //取第一个非叶子节点开始堆化
19         for (int i = n/2 - 1; i >= 0; --i)
20         {
21             heapfiy(A, n - 1, i);
22         }
23     }
24     
25     //堆化
26     void heapfiy(int* A, int n, int k)
27     {
28         //先设置默认的最大节点
29         int maxPos = k;
30         while (true)
31         {
32             //先查看当前节点的左子树
33             if (2 * k + 1 <= n && A[2 * k + 1] > A[maxPos])
34                 maxPos = 2 * k + 1;
35             //查看右子树
36             if (2 * k + 2 <= n && A[2 * k + 2] > A[maxPos])
37                 maxPos = 2 * k +2;
38             if (maxPos == k)
39                 break;
40             swap(A, k, maxPos);
41             k = maxPos;
42         }
43     }
44     
45     void swap(int* A, int m, int n)
46     {
47         if (A == NULL)
48             return ;
49         int temp = A[m];
50         A[m] = A[n];
51         A[n] = temp;
52     }
53 };

 在理解了堆排序的思路后,代码实现的时候,需要注意数各个操作的上限问题,不能越界,临界值的处理也要注意。

堆排序

原文:https://www.cnblogs.com/kks170716/p/11042508.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!