文档章节

堆排序原理及算法实现(最大堆)

KMSFan
 KMSFan
发布于 2014/12/21 18:40
字数 1333
阅读 131
收藏 0

堆排序

       堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。

1.堆

  堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:

  Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

  即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

  堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

   利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

    其基本思想为(大顶堆):

    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无须区;

    2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 

    3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

    操作过程如下:

     1)初始化堆:将R[1..n]构造为堆;

     2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。

    因此对于堆排序,最重要的两个操作就是构造初始堆和调整堆,其实构造初始堆事实上也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整。

    下面举例说明:

     给定一个整形数组a[]={16,7,3,20,17,8},对其进行堆排序。

    首先根据该数组元素构建一个完全二叉树,得到

 

 然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:

20和16交换后导致16不满足堆的性质,因此需重新调整

这样就得到了初始堆。

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

此时3位于堆顶不满堆的性质,则需调整继续调整

 这样整个区间便已经有序了。

    从上述过程可知,堆排序其实也是一种选择排序,是一种树形选择排序。只不过直接选择排序中,为了从R[1...n]中选择最大记录,需比较n-1次,然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过,而树形选择排序恰好利用树形的特点保存了部分前面的比较结果,因此可以减少比较次数。对于n个关键字序列,最坏情况下每个节点需比较log2(n)次,因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序,不适合记录较少的排序。

 

测试程序

复制代码

/*堆排序(大顶堆) 2011.9.14*/ #include <iostream>
#include<algorithm>using namespace std;void HeapAdjust(int *a,int i,int size)  //调整堆 {    int lchild=2*i;       //i的左孩子节点序号     int rchild=2*i+1;     //i的右孩子节点序号     int max=i;            //临时变量     if(i<=size/2)          //如果i不是叶节点就不用进行调整     {        if(lchild<=size&&a[lchild]>a[max])
        {
            max=lchild;
        }    
        if(rchild<=size&&a[rchild]>a[max])
        {
            max=rchild;
        }        if(max!=i)
        {
            swap(a[i],a[max]);
            HeapAdjust(a,max,size);    //避免调整之后以max为父节点的子树不是堆         }
    }        
}void BuildHeap(int *a,int size)    //建立堆 {    int i;    for(i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2     {
        HeapAdjust(a,i,size);    
    }    
} 

void HeapSort(int *a,int size)    //堆排序 {    int i;
    BuildHeap(a,size);    for(i=size;i>=1;i--)
    {        //cout<<a[1]<<" ";        swap(a[1],a[i]);           //交换堆顶和最后一个元素,即每次将剩余元素中的最大者放到最后面 
          //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆           HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆    }
} 

int main(int argc, char *argv[])
{     //int a[]={0,16,20,3,11,17,8};    int a[100];    int size;    while(scanf("%d",&size)==1&&size>0)
    {        int i;        for(i=1;i<=size;i++)
            cin>>a[i];
        HeapSort(a,size);        for(i=1;i<=size;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }    return 0;
}

复制代码



本文转载自:http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621

共有 人打赏支持
KMSFan

KMSFan

粉丝 18
博文 5
码字总数 23309
作品 0
长沙
私信 提问
视频 | 手撕九大经典排序算法,看我就够了!

视频 | 手撕九大经典排序算法,看我就够了! { } { } { } void countSort(int arr[], int n, int exp){ } void radixsort(int arr[], int n){ } { } { } void mergeSort(int arr[], int l, ......

力扣(LeetCode)
02/05
0
0
JavaScript数据结构与算法(堆)

堆是一种完全二叉树. 堆得使用基本是通过最大堆和最小堆来实现的! 最大堆,最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点 最小堆,最小堆中的最大元...

fiveoneLei
2018/07/12
0
0
Heapsort 和 priority queue

一、二叉堆含义及属性: 堆(heap)亦被称为:优先队列(priority queue),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。在队列中,调度程序反...

famince
2014/07/30
0
0
排序算法总结(python版)

经典排序算法总结与实现 经典排序算法在面试中占有很大的比重,也是基础,为了未雨绸缪,在寒假里整理并用Python实现了七大经典排序算法,包括冒泡排序,插入排序,选择排序,希尔排序,归并...

dby_freedom
2018/08/28
0
0
算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队列:出队顺序和入队顺序无关;和优先级相关 为什么使...

天涯明月笙
2017/09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

容器服务

简介 容器服务提供高性能可伸缩的容器应用管理服务,支持用 Docker 和 Kubernetes 进行容器化应用的生命周期管理,提供多种应用发布方式和持续交付能力并支持微服务架构。 产品架构 容器服务...

狼王黄师傅
昨天
3
0
高性能应用缓存设计方案

为什么 不管是刻意或者偶尔看其他大神或者大师在讨论高性能架构时,自己都是认真的去看缓存是怎么用呢?认认真真的看完发现缓存这一块他们说的都是一个WebApp或者服务的缓存结构或者缓存实现...

呼呼南风
昨天
12
0
寻找一种易于理解的一致性算法(扩展版)

摘要 Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可...

Tiny熊
昨天
3
0
聊聊GarbageCollectionNotificationInfo

序 本文主要研究一下GarbageCollectionNotificationInfo CompositeData java.management/javax/management/openmbean/CompositeData.java public interface CompositeData { public Co......

go4it
昨天
3
0
阿里云ECS的1M带宽理解

本文就给大家科普下阿里云ECS的固定1M带宽的含义。 “下行带宽”和“上行带宽” 为了更好的理解,需要先给大家解释个词“下行带宽”和“上行带宽”: 下行带宽:粗略的解释就是下载数据的最大...

echojson
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部