HeapSort 堆排序(内含Floyd建堆算法)

二叉堆

二叉堆是一棵完全二叉树,且任意一个结点的键值总是小于或等于其子结点的键值(最小堆)。
二叉堆采用数组来存储(按广度优先遍历的顺序),而没有像普通的树结构使用指针来表示节点间的关系。


堆示意图.jpg
  • 最大堆:父结点的键值总是大于或等于任何一个子结点的键值;最大堆常用于排序算法。
  • 最小堆:父结点的键值总是小于或等于任何一个子结点的键值;最小堆常用于优先队列。

堆的意义就在于:最快的找到最大/最小值,在堆结构中插入一个值重新构造堆结构,取走最大/最下值后重新构造堆结构;其时间复杂度为O(logN);

堆排序

所谓堆排序,就是先建立N个元素的二叉堆,花费O(N)时间,然后执行N次deleteMax操作,每个deleteMax花费O(logN)时间,因此总的运行时间是O(NlogN)。
为了节约空间,每次deleteMax之后,堆缩小了1,所以可以用堆中最后的单元来存放刚刚删去的元素,这样不需要额外空间。
下面是《数据结构与算法分析:C++描述》(第3版)199页堆排序代码


template <typename Comparable>
void heapsort(vector<Comparable> & a){
    //建堆,只需要从size的一半开始下滤就够了
    for (int i = a.size() / 2; i >= 0;--i)  
        percDown(a, i, a.size());
    for (int j = a.size() - 1; j > 0;j--){
        swap(a[0], a[j]);
        percDown(a, 0, j);
    }
}

//返回堆中第i个元素的左儿子,注意这里堆数组从0开始
inline int leftChild(int i){    
    return 2 * i + 1;
}

//i是需要下滤的节点,n是堆的大小
template <typename Comparable>
void percDown(vector<Comparable> &a, int i, int n){    
    Comparable temp;
    int child;
    //先把要下滤的值a[i]存在temp里
    for (temp = a[i]; leftChild(i)< n;i = child){   //终止条件,左儿子超出堆大小
        child = leftChild(i);   //找到左儿子节点
        //如果右儿子存在且比左儿子大,选择右儿子
        if(child != n-1&& a[child+1]>a[child])  
            child++;
        if(temp < a[child]) //儿子比老子大,儿子上位
            a[i] = a[child];
        else                //儿子比老子小,那么找到下滤值该放的位置了
            break;
    }
    a[i] = temp;    //把下滤值放到a[i]
}

最后放上大佬总结的heapsort.cpp
ClassicalCode:heapSort.cpp

求前K大(小)的数

利用最小堆和最大堆可以求一个包含N个元素的数组的前K大(或小)的数,原理如下:

我们首先取这N个元素中的前K个元素来建立一个由K个元素组成的小(大)顶堆,这样堆顶元素便是当前已读取元素中的第K大(小)者;然后,依次读取剩下的N-K个元素,而对于其中的每个元素x,若x大于(小于)当前的堆顶元素,则将堆顶元素替换为x,并自堆顶至向下调整堆;这样,在读取完所有元素后,堆中的K个元素即为这N个数中的前K个最大(小)元素,同时堆顶元素为这N个数中的第K大(小)元素。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,747评论 0 15
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,223评论 0 52
  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 2,368评论 0 3
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,286评论 0 2
  • 出门旅行,尤其是夏季,在所难免会碰到阴天下雨的时候。其实,对于摄影来说雨天也是一种大自然的恩惠,往往在雨天能创造出...
    明先森吖阅读 580评论 6 18