堆排序

简介: 堆排序

heapSort

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆排序可以说是一种利用堆的概念来排序的选择排序

  1. 底层使用数组data来实现堆
  2. 插入方法:把插入的元素放到数组末尾,进行shiftUp操作,上浮到合适位置
  3. 提取最大值:把根元素与末尾元素交换,再对交换后的根元素进行shiftDown操作,下沉到合适位置
  4. 遍历要排序的数组arr,把元素插入堆中
  5. 从堆中提取出最值,再赋值给arr,排序完成

#include<iostream>

#include<algorithm>

#include<cassert>

#include<ctime>

usingnamespacestd;

template<typenameItem>

classMaxHeap {

   private:

       Item*data;

       intcount;

       intcapacity;

       //上浮:将索引为k的元素上浮到合适位置

       voidshiftUp(intk) {

           //与父节点比较,直到小于或等于父节点

           while(k>1&&data[k]>data[k/2]) { //当前节点data[k]大于父节点,要进行上浮,k最少在第二层才能跟父节点比较

               swap(data[k],data[k/2]);

               k/=2;

           }

       }

       voidshiftDown(intk){

           //左孩子坐标小于等于count(存在孩子),count是最后元素的坐标

           while(2*k<=count){

               intj=2*k;//在此轮循环中data[k]与data[j]交换

               //判断是否存在右孩子并且右孩子大于左孩子

               if(j+1<=count&&data[j+1]>data[j])

                   j+=1;

               //将当前节点与子节点中的最大子进行比较

               if(data[k]>=data[j])//当前节点大于等于两个子节点,说明已经到达合适位置,直接跳出循环

                   break;

               else {

                   swap(data[j],data[k]);//否则,将他们进行交换

                   k=j;

               }

           }

       }  

   public:

       MaxHeap(intcapacity) {

           //因为我们的数组下标从1开始

           data=newItem[capacity+1];

           count=0;

           this->capacity=capacity;

       }

       //heapify:将一个数组整理成堆

       MaxHeap(Itemarr[],intn){

           //开辟空间,Item类型的数组

           data=newItem[n+1];

           capacity=n;

           //把arr赋值到data

           for(inti=0;i<n;i++)

               data[i+1]=arr[i];

           count=n;

           //从第一个非叶子节点开始,进行下沉操作,直到根节点

           for(inti=count/2;i>=1;i--)

               shiftDown(i);

       }

       

       ~MaxHeap() {

           delete [] data;

       }

       intsize() {

           returncount;

       }

       boolisEmpty() {

           returncount==0;

       }

       voidinsert(Itemitem) {

           //防止越界

           assert(count+1<=capacity);

           //从下标1开始,把元素放到数组末尾,即在二叉堆的最后

           data[count+1]=item;

           count++;

           //shiftUp:上浮

           shiftUp(count);

       }

       //提取最大值

       ItemextractMax(){

           assert(count>0);

           //保存根节点,最后返回

           Itemret=data[1];

           //将根节点与末尾节点交换

           swap(data[1],data[count]);

           count--;

           //下沉

           shiftDown(1);

           returnret;

       }

};

template<typenameT>

voidheapSort1(Tarr[],intn){

   MaxHeap<T>maxHeap(n);

   for(inti=0;i<n;i++)

       maxHeap.insert(arr[i]);

   //最大堆取出是从大到小,我们想要数组是从小到大,从后往前赋值即可

   for(inti=n-1;i>=0;i--)

       arr[i]=maxHeap.extractMax();

}

heapSort1中是将未排序数组arr的元素一个一个的插入到最大堆中,可以进行优化——堆化(heapify):把一个无序整数数组变成一个堆数组

heapify优化

从最后一个非叶子节点开始进行siftdown操作,直到根节点,最后形成最大堆(所有的叶子节点已经是最大堆,无需再考虑,直接省略n/2个元素的操作,大大优化时间复杂度)

最后一个非叶子节点的索引

用数组来表示完全二叉树,如何定位最后一个非叶子节点的索引?

当数组从索引1开始存储,已知一个节点索引为i

  1. 节点父节点的索引=i/2
  2. 节点左孩子的索引=2*i
  3. 节点右孩子的索引=2*i+1
  4. 最后一个非叶子节点的索引=最后一个节点的父节点索引=count/2(当前count==索引i)

当数组从索引0开始存储,已知一个节点索引为i

  1. 节点父节点的索引=(i-1)/2
  2. 节点左孩子的索引=2*i+1
  3. 节点右孩子的索引=2*i+2
  4. 最后一个非叶子节点的索引=最后一个节点的父节点索引=((count-1)-1)/2(当前count==索引i+1,count是即将要插入元素的索引)

heapify

将heapify过程设置为构造函数,用户传来数组,即可将其heapify

       //heapify:将一个数组整理成堆

       MaxHeap(Itemarr[],intn){

           //开辟空间,Item类型的数组

           data=newItem[n+1];

           capacity=n;

           //把arr赋值到data

           for(inti=0;i<n;i++)

               data[i+1]=arr[i];

           count=n;

           //从第一个非叶子节点开始,进行下沉操作,直到根节点,就在data数组中实现了arr的堆化

           for(inti=count/2;i>=1;i--)

               shiftDown(i);

       }

template<typenameT>

voidheapSort2(Tarr[],intn){

   MaxHeap<T>maxHeap=MaxHeap<T>(arr,n);

   //最大堆取出是从大到小,我们想要数组是从小到大,从后往前赋值即可

   for(inti=n-1;i>=0;i--)

       arr[i]=maxHeap.extractMax();

}

比较

  1. 将n个元素依次插入到一个空堆中,时间复杂度为O(nlogn)
  2. heapify过程的时间复杂度为O(n)

上面的两种方法都是先将未排序数组放入堆中,再将其从堆中取出,空间复杂度是O(n)

原地堆排序

直接在要排序数组中进行堆化操作,无需开辟新的空间,空间复杂度是O(1)

  1. 通过heapify过程将一个数组构建成最大堆,数组首元素就是最大堆中的最大值v

  2. 首元素与末尾元素交换,交换后最大值已经到达正确位置,下次排序不用再对其操作

    此时橙色部分因首元素的存在而不再是最大堆,那么对首元素进行shiftDown操作,使之再次成为最大堆

  3. 针对最大堆重复操作1、2,直到全部变为蓝色

注意:由于整个排序过程在数组上进行,而通常数组是从0开始索引的

template<typenameT>

void__shiftDown(Tarr[],intn,intk){//k是进行下沉操作的索引

   //1.左孩子不越界

   while(2*k+1<n){

       intj=2*k+1;

       //2.右孩子不越界且大于左孩子,重新赋值j

       if(j+1<n&&arr[j]<arr[j+1])

           j+=1;

       //3.当前节点大于等于孩子节点,结束下沉

       if(arr[k]>=arr[j])

           break;

       //4.当前节点小于孩子节点,下沉

       swap(arr[k],arr[j]);

       k=j;

   }

}

template<typenameT>

voidheapSort(Tarr[],intn){

   //heapify操作:将arr数组构建成了一个堆

   // 注意,此时我们的堆是从0开始索引的

   // 从(最后一个元素的索引-1)/2开始

   // 最后一个元素的索引 = n-1

   for(inti=((n-1)-1)/2;i>=0;i--)

       __shiftDown(arr,n,i);

   for(inti=n-1;i>0;i--){

       //将首元素与末尾元素交换

       swap(arr[i],arr[0]);

       //对首元素进行下沉操作

       __shiftDown(arr,i,0); //每循环一次,未排序数组元素就少一个

   }

}


目录
相关文章
|
2月前
|
存储 搜索推荐 算法
堆排序讲解
堆排序讲解
22 4
|
5月前
|
存储
|
6月前
|
分布式计算 搜索推荐 Java
堆排序就是这么容易
堆排序就是这么容易
49 0
|
7月前
|
算法 搜索推荐 Java
选择排序 - 堆排序
选择排序 - 堆排序
选择排序 - 堆排序
|
7月前
|
搜索推荐 算法
【排序算法】堆排序详解与实现
【排序算法】堆排序详解与实现
|
7月前
|
搜索推荐 算法 C++
C++堆排序的实现
C++堆排序的实现
|
7月前
选择排序与堆排序
选择排序与堆排序
41 0
|
7月前
|
算法 搜索推荐 索引
堆排序详细解读
堆排序详细解读
62 0
|
算法 索引 搜索推荐
|
机器学习/深度学习 算法 搜索推荐
排序算法:堆排序
关于排序算法中的堆排序的详细介绍,以及实现过程和时间复杂度的计算,附带图解。
114 1