FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

堆排序(Heap Sort)算法学习

FunctionGHW posted @ 2013年10月29日 21:54 in 算法学习 with tags 排序 in-place heap sort max heap , 7509 阅读

堆排序可以看作选择排序的进化版。选择排序通过遍历来选出最大(最小)元素, 堆排序利用数据结构二叉堆更快的选出最大(最小)元素。堆排序有两个优势: 1.)最好、最坏和平均时间复杂度均为\(O(nlogn)\); 2.)可以原地进行,空间复杂度\(O(1)\)。

最大(最小)堆的性质

二叉堆通常是一个数组, 可以被看作完全(或近似完全)二叉树。

  • 一个二叉堆是最大堆,则满足如下条件:
    对任意的节点 \(i\),如果存在父节点\(parent(i)\),则必有\(parent(i) \ge i\)。
  • 一个二叉堆是最小堆,则满足如下条件:
    对任意的节点 \(i\),如果存在父节点\(parent(i)\),则必有\(parent(i) \le i\)。

由最大(小)堆的性质不难推出: 最大(小)值在树的根上。

堆排序算法

堆排序的基本思路如下:

  1. 把待排序数组构造成一个最大堆
  2. 取出树的根(最大(小)值, 实际算法的实现并不是真正的取出)
  3. 将树中剩下的元素再构造成一个最大堆(这里的构造和第1步不一样,具体看实现部分)
  4. 重复2,3操作,直到取完所有的元素
  5. 把元素按取出的顺序排列,即得到一个有序数组(在代码实现里是通过交换操作"无形中"完成的)
在开始实现算法先看几个结论(证明略):
  • 完全二叉树A[0:n-1]中的任意节点,其下标为 \(i\), 那么其子节点的下标分别是为\(2i + 1\) 和 \(2(i + 1)\)
  • 大小为n的完全二叉树A[0:n-1],叶子节点中下标最小的是\(\lfloor \frac {n}{2} \rfloor\), 非叶子节点中下标最大的是\(\lfloor \frac {n}{2} \rfloor - 1\)
  • 如果数组是一个最大堆,那么最大元素就是A[0]
  • 最大堆中任意节点的左右子树也是最大堆

 

这里的算法实现使用的是最大堆,首先来解决由数组建立最大堆的问题:

// 用于计算下标为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(\log n)\)。函数build_max_heap自底向上的调用max_heapify, 最终整个数组满足最大堆,迭代过程的复杂度为\(O(n\log n)\), 因此整个函数的最坏时间复杂度也是\(O(n\log n)\)。 而如果当前数组已经是最大堆了,例如数组原本是降序排列的, 那么max_heapify过程的时间复杂度就是\(O(1)\), 此时build_max_heap的时间复杂度是\(O(n)\),这是最好的情况。

接着实现堆排序过程:

/* 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(n\log n)\), 所以整个算法的最好最坏和平均时间复杂度都是\(O(n\log n)\)。

堆排序算法的空间复杂度是\(O(1)\),从实现上很容易看出来。

Liwovosa 说:
2021年4月19日 15:42

I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much. 123movies

jackjohnny 说:
2021年6月05日 22:52

I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much. indian visa online

jackjohnny 说:
2021年6月18日 01:08

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. 먹튀사이트

jackjohnny 说:
2021年6月26日 23:02

I read a article under the same title some time ago, but this articles quality is much, much better. How you do this.. 안전놀이터

jackjohnny 说:
2021年6月30日 01:50

Please continue this great work and I look forward to more of your awesome blog posts. new zealand visa application

jackjohnny 说:
2021年7月05日 20:18

You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant! สล็อต

jackjohnny 说:
2021年7月12日 14:41

This is such a great resource that you are providing and you give it away for free. 안전놀이터

Liwovosa 说:
2022年1月17日 22:06 Thank you so much for the post you do. I like your post and all you share with us is up to date and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job. 소액결제 현금화
Liwovosa 说:
2022年1月19日 19:36

Great job here on _______ I read a lot of blog posts, but I never heard a topic like this. I Love this topic you made about the blogger's bucket list. Very resourceful. 셔츠룸

Liwovosa 说:
2022年1月28日 04:19

Thank you for the update, very nice site.. Magazine Tutorial USA

market1 说:
2022年1月29日 18:41

Very efficiently written information. It will be beneficial to anybody who utilizes it, including me. Keep up the good work. For sure i will check out more posts. This site seems to get a good amount of visitors. <a href="https://www.northamericanbancard.pro">North American Bancard Sales Partner</a>

market1 说:
2022年1月29日 18:42

Very efficiently written information. It will be beneficial to anybody who utilizes it, including me. Keep up the good work. For sure i will check out more posts. This site seems to get a good amount of visitors. North American Bancard Sales Partner

SEO 说:
2022年2月11日 19:14

Great things you’ve always shared with us. Just keep writing this kind of posts.The time which was wasted in traveling for tuition now it can be used for studies.Thanks noodle magazine

SEO 说:
2022年2月24日 02:18

I appreciated your work very thanks https://voyance-tel-avenir.com/

SEO 说:
2022年3月15日 13:13

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work! บาคาร่า ฝากถอน ไม่มีขั้นต่ํา

smart 说:
2022年3月19日 04:07

Very interesting information, worth recommending. However, I recommend this: <a href="https://guslot88.com/free-credit-guslot/">gus88 wallet</a>

SEO 说:
2022年4月07日 19:14

I can’t imagine focusing long enough to research; much less write this kind of article. You’ve outdone yourself with this material. This is great content. export instagram comments into excel

jackseo 说:
2022年4月09日 06:14

Thanks for a wonderful share. Your article has proved your hard work and experience you have got in this field. Brilliant .i love it reading. detectives privados en málaga

SEO 说:
2022年4月11日 04:43

i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. 슬롯게임

SEO 说:
2022年4月11日 15:45

Succeed! It could be one of the most useful blogs we have ever come across on the subject. Excellent info! I’m also an expert in this topic so I can understand your effort very well. Thanks for the huge help. tiktok analytics

SEO 说:
2022年4月12日 02:04

Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. click here

SEO 说:
2022年4月13日 17:29

Thank you so much for such a well-written article. It’s full of insightful information. Your point of view is the best among many without fail.For certain, It is one of the best blogs in my opinion. 우리카지노

https://vivanet2.com 说:
2022年4月15日 21:01

https://vivanet2.com/?fbclid=IwAR1ay9OWrt9zTDYeb7NAQjT91L90xMCZp4OiYnCLonCMgx-xrW4sGr-YfyU

SEO123 说:
2022年4月16日 15:08

very nice post, i surely really like this amazing site, persist with it

SEO 说:
2022年4月17日 12:56

It is my first visit to your blog, and I am very impressed with the articles that you serve. Give adequate knowledge for me. Thank you for sharing useful material. I will be back for the more great post. concept product design

SEO 说:
2022年4月23日 18:35

I have bookmarked your blog, the articles are way better than other similar blogs.. thanks for a great blog! Search Properties for rent in Mortdale NSW 2223

William Johnson 说:
2022年4月29日 14:57

I use as shown by a general viewpoint goliath materials - you can see them at: magazine module

seo 说:
2022年5月16日 03:35

Nice knowledge gaining article. This post is really the best on this valuable topic. logic pro vocal presets

seo 说:
2022年5月16日 20:40

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. духи дежавю

William Johnson 说:
2022年5月17日 03:43

I favor dependably stunning resources - you will see these people in: Buy Nipple Clamps

seo 说:
2022年5月17日 18:21

This was really an interesting topic and I kinda agree with what you have mentioned here! Virgin body wave

SEO 说:
2022年5月23日 00:47

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. 제주풀싸롱

SEO 说:
2022年5月24日 20:10 I think that thanks for the valuabe information and insights you have so provided here. green suits
seo 说:
2022年5月25日 20:37

No doubt this is an excellent post I got a lot of knowledge after reading good luck. Theme of blog is excellent there is almost everything to read, Brilliant post. 먹튀

seo 说:
2022年5月30日 15:03

Please continue this great work and I look forward to more of your awesome blog posts. บาคาร่า

seo 说:
2022年6月05日 20:34

I would like to say that this blog really convinced me to do it! Thanks, very good post. สล็อต ออนไลน์

seo 说:
2022年6月06日 14:20

Excellent article. Very interesting to read. I really love to read such a nice article. Thanks! keep rocking. slot jili

SEO 说:
2022年6月08日 01:14

Oppo Reno5 K Specs, Reviews and Price in Pakistan, MLT World offers all information about this phone.

qk 说:
2022年6月09日 21:49

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. 카지노사이트

William Johnson 说:
2022年7月05日 13:04

wow this upstanding notwithstanding ,I love your enter offering little appreciation to titanic pics might be part personss not a monster store of occupied with sexual relations being defrent mind all around poeple , Cafe Astrology

William Johnson 说:
2022年7月21日 20:10

Well… I discharge up battles on an on a focal level inadequately portrayed from issue, at any rate I never visited your blog. I added it to populars correspondingly i'll be your solid foundation. the test tech

William Johnson 说:
2022年7月21日 20:16

I can propose on a standard level striking and unimaginably strong tips, in this way see it: nh craigslist

William Johnson 说:
2022年7月21日 20:40
 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter