首页 > 算法 > 算法系列之 堆排序

算法系列之 堆排序

二叉堆的性质

  1. 二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的
  2. 最小堆父结点小于等于其每一个子结点的键值,最大堆则相反
  3. 每个结点的左子树或者右子树都是一个二叉堆

下面是一个最小堆:
Image

堆的存储

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中:

  • 父节点i的左子节点在位置 (2*i+1);
  • 父节点i的右子节点在位置 (2*i+2);
  • 子节点i的父节点在位置 floor((i-1)/2);

0_1314014706gZqn

堆的操作图解——建立插入与删除

摘自《数据结构C++语言描述》最小堆的建立、插入与删除的图解:
Image

堆的插入

参照堆的操作图解中的堆的插入,对于插入的a[i]元素,前面的a[0...i-1]已经是一个最小堆,接下来就是把a[i]插入到a[0...i-1]的适当位置,这个过程跟之前的插入排序算法类似(链接:),插入排序算法i是跟前面的i-1元素比较,而这里i是跟父结点比较而已。

//将a[i]插入到最小堆a[0...i-1]中的适当位置,形成更大的最小堆a[0...i],类似于插入排序
void MinHeapFixUp(int a[], int i)
{
     int j,temp;
     temp = a[i];
     for (j = (i - 1)/2; j >= 0; j = (i-1)/2) //j为父结点
     {
          if (a[j] > temp)
          {
               a[i] = a[j]; //把较大的父结点往下移动,替换它的子结点 
               i = j;
          }
          else
          {
               break;
          }
     }
     a[i] = temp;
}

//在最小堆的索引为n处插入新的数据num
void MinHeapAddNumber(int a[], int n, int num) 
{ 
    a[n] = num; 
    MinHeapFixUp(a, n); 
}

堆的删除

参照堆的操作图解中的堆的删除操作,说到删除总是发生在根a[0]处,然后最后一个元素被用来填补空缺位置。
对于堆排序来讲,其实我们的做法是将最后一个元素n-1跟元素0互换位置,然后对a[0]在a[0...n-2]中进行一次自上至下的重建堆。堆的插入重建堆是自下而上,而这里堆的删除重建堆是自上而下,算法相类似,只不过方向相反,并且堆的删除要取左右子结点最最小的

//对a[i]进行自上而下的重建堆,n为结点总数,类似于插入排序
void MinHeapFixDown(int a[], int i, int n)
{
     int temp = a[i];
     for (int j = 2 * i + 1; j < n ; j = 2 * i + 1) //j为子结点
     {
          if (j + 1 < n && a[j + 1] > a[j])
          {
               j = j + 1; //在左右结点中找最小的
          }
          if (a[j] < a[i])
          {
               a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点
               i = j;
          }
          else
          {
               break;
          }
     }
     a[i] = temp;
}

//删除最小节点
void MaxHeapDeleteElement(int a[], int n)
{
     //交换
     Swap(a[0], a[n-1]);
     //删除
     MinHeapFixDown(a, 0, n-1);
}

堆化数组

一开始,对叶子结点来说,可以认为它已经是一个合法的堆了。所以我们只需从最后一个非叶子结点开始进行堆化。

怎么求出最后一个非叶子结点的索引:
最后一个叶子结点的索引为n-1。其父亲结点位于索引parentPos = ((n-1)-1)/2 = (n-2)/2 = n/2 – 1
该处定义了堆中最后一个非叶子结点,该父亲结点给出了堆化数组的起始索引。

我们对parentPos 到0范围内的索引执行重建堆的操作MinHeapFixUp,便完成了堆化数组的操作。

如下图所示的一次堆化数组的过程,最后一个非叶子结点是a[3],也就是第4个结点91。
Image

//堆化数组建立最小堆
void MakeMinHeap(int a[], int n)
{
     for (int i = n/2 -1; i >= 0; i--)
     {
          MinHeapFixDown(a, i, n);
     }
}

堆排序

首先执行堆化数组,堆化数组建好最小堆后,我们发现最小堆的根元素a[0]总是最小的元素,这时候我们可以对a[0...n-1]的a[0]执行一次上文说的堆的删除,也就是Swap(a[0],a[n-1]),然后在a[0...n-2]中对a[0]进行一次自上而下的堆的重建,执行后a[n-1]存放的便是最小值,然后a[0...n-2]依然是剩下的元素的最小堆。接着对a[0...n-2]的a[0]执行一次删除,执行后a[n-2]存放的便是第二小的值,然后a[0...n-3]依然是剩下的元素的最小堆。依次类推,直到执行完对a[0...1]的堆的删除后,这个堆就是有序的从大到小的序列了

//堆排序
void MinHeapSort(int a[], int n)
{
     //堆化数组,建立最小堆
     MakeMinHeap(a, n);
     for (int i = n-1; i > 0; i--)
     {
          Swap(a[i], a[0]);
          MinHeapFixDown(a, 0, i);
     }
}

注意使用最小堆排序后是递减数组,要得到递增数组,可以使用最大堆。

时间复杂度:

建堆需要做N/2次向下堆的调整,每次调整时间复杂度为logN
进行N-1次堆顶的删除,删除后每次堆的调整时间复杂度为logN
两次操作时间相加还是NlogN,故时间复杂度为NlogN

空间复杂度:

空间复杂度为1,只需要临变量,不需要其它额外的变量

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.