排序系列之——再叙堆排序

在我之前的文章中:《高效排序之——堆排序,归并排序、快速排序》中初步介绍了堆排序的过程,但是认真的说,自己并没有叙述的十分清楚,这篇博客,我将持续更新,表明堆排序的一个过程和核心思想。

系列博客将按照下面三个问题展开:

  1. 什么是堆?
  2. 为何堆结构可以用来排序?
  3. 怎么利用堆结构进行排序?
  4. 堆排序的算法性能如何?
  5. 总结堆的特性

本文将先回答前两个问题:

  1. 什么是堆结构?

堆结构是一棵完全二叉树,这是堆结构最为根本的性质;当然,我们通常会讨论最大堆结构和最小堆结构。这里以最大堆结构为例,说明最大堆的特点:排序系列之——再叙堆排序

上图所示为一个最大堆结构,很明显需要满足以下两点:1 必须满足堆结构的定义:完全二叉树;2 任何一个子节点的值都不大于其父节点的值

第一个问题回答完毕,再来回答第二个问题:为何堆结构可以用来排序?

那么这个问题就要说到优先队列事情了。队列结构——先进先出,而优先队列呢,满足优先级别高的先出。等等,这和堆结构有何关系呢?,

我们来看看上述最大堆结构:最大堆结构 和优先队列联系起来的 纽带是:越上层的父节点,其优先级越高,我们将上述最大堆直接写成一个数组结构:

排序系列之——再叙堆排序如果把该数组看成队列结构,那么优先出队列的则是元素“45”。最大堆的性质导致了堆的一个很重要的特性:根节点是堆里面数值最大的元素。所以,当元素45出堆后,剩下的元素中最大的元素必然要上浮到根节点的位置。因此,根据堆结构的这一出堆的性质,将一个堆结构所有元素全部出堆,就构成了一个有序列,即完成了排序的功能。

因此堆排序的核心其实是两步:将待排序数组构建为一个堆结构;2 将根节点出堆  

仔细思考上面的两个步骤,本质上是两个相反的过程:将n个元素插入一个空堆;将这n个元素按照出堆原则出堆

在此,给出两个基本结论:将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn)。当然也可以采用heapify算法,将建堆过程的复杂度降低到O(n),该算法的核心思想是:直接对原数组进行结构调整,而且我们开始调整的位置从n/2-1.

至此,博客回答了前两个问题,后续问题会定期更新!

相关推荐