heapSort
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆排序可以说是一种利用堆的概念来排序的选择排序
- 底层使用数组data来实现堆
- 插入方法:把插入的元素放到数组末尾,进行shiftUp操作,上浮到合适位置
- 提取最大值:把根元素与末尾元素交换,再对交换后的根元素进行shiftDown操作,下沉到合适位置
- 遍历要排序的数组arr,把元素插入堆中
- 从堆中提取出最值,再赋值给arr,排序完成
#include<iostream>
#include<algorithm>
#include<cassert>
#include<ctime>
using namespace std;
template<typename Item>
class MaxHeap {
private:
Item* data;
int count;
int capacity;
//上浮:将索引为k的元素上浮到合适位置
void shiftUp(int k) {
//与父节点比较,直到小于或等于父节点
while(k>1&&data[k]>data[k/2]) { //当前节点data[k]大于父节点,要进行上浮,k最少在第二层才能跟父节点比较
swap(data[k],data[k/2]);
k/=2;
}
}
void shiftDown(int k){
//左孩子坐标小于等于count(存在孩子),count是最后元素的坐标
while(2*k<=count){
int j=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(int capacity) {
//因为我们的数组下标从1开始
data=new Item[capacity+1];
count=0;
this->capacity=capacity;
}
//heapify:将一个数组整理成堆
MaxHeap(Item arr[],int n){
//开辟空间,Item类型的数组
data=new Item[n+1];
capacity=n;
//把arr赋值到data
for(int i=0;i<n;i++)
data[i+1]=arr[i];
count=n;
//从第一个非叶子节点开始,进行下沉操作,直到根节点
for(int i=count/2;i>=1;i--)
shiftDown(i);
}
~MaxHeap() {
delete [] data;
}
int size() {
return count;
}
bool isEmpty() {
return count==0;
}
void insert(Item item) {
//防止越界
assert(count+1<=capacity);
//从下标1开始,把元素放到数组末尾,即在二叉堆的最后
data[count+1]=item;
count++;
//shiftUp:上浮
shiftUp(count);
}
//提取最大值
Item extractMax(){
assert(count>0);
//保存根节点,最后返回
Item ret=data[1];
//将根节点与末尾节点交换
swap(data[1],data[count]);
count--;
//下沉
shiftDown(1);
return ret;
}
};
template<typename T>
void heapSort1(T arr[],int n){
MaxHeap<T> maxHeap(n);
for(int i=0;i<n;i++)
maxHeap.insert(arr[i]);
//最大堆取出是从大到小,我们想要数组是从小到大,从后往前赋值即可
for(int i=n-1;i>=0;i--)
arr[i]=maxHeap.extractMax();
}
heapSort1中是将未排序数组arr的元素一个一个的插入到最大堆中,可以进行优化——堆化(heapify):把一个无序整数数组变成一个堆数组
heapify优化
从最后一个非叶子节点开始进行siftdown操作,直到根节点,最后形成最大堆(所有的叶子节点已经是最大堆,无需再考虑,直接省略n/2个元素的操作,大大优化时间复杂度)
最后一个非叶子节点的索引
用数组来表示完全二叉树,如何定位最后一个非叶子节点的索引?
当数组从索引1开始存储,已知一个节点索引为i
- 节点父节点的索引=i/2
- 节点左孩子的索引=2*i
- 节点右孩子的索引=2*i+1
- 最后一个非叶子节点的索引=最后一个节点的父节点索引=count/2(当前count==索引i)
当数组从索引0开始存储,已知一个节点索引为i
- 节点父节点的索引=(i-1)/2
- 节点左孩子的索引=2*i+1
- 节点右孩子的索引=2*i+2
- 最后一个非叶子节点的索引=最后一个节点的父节点索引=((count-1)-1)/2(当前count==索引i+1,count是即将要插入元素的索引)
heapify
将heapify过程设置为构造函数,用户传来数组,即可将其heapify
//heapify:将一个数组整理成堆
MaxHeap(Item arr[],int n){
//开辟空间,Item类型的数组
data=new Item[n+1];
capacity=n;
//把arr赋值到data
for(int i=0;i<n;i++)
data[i+1]=arr[i];
count=n;
//从第一个非叶子节点开始,进行下沉操作,直到根节点,就在data数组中实现了arr的堆化
for(int i=count/2;i>=1;i--)
shiftDown(i);
}
template<typename T>
void heapSort2(T arr[],int n){
MaxHeap<T> maxHeap=MaxHeap<T>(arr,n);
//最大堆取出是从大到小,我们想要数组是从小到大,从后往前赋值即可
for(int i=n-1;i>=0;i--)
arr[i]=maxHeap.extractMax();
}
比较
- 将n个元素依次插入到一个空堆中,时间复杂度为O(nlogn)
- heapify过程的时间复杂度为O(n)
上面的两种方法都是先将未排序数组放入堆中,再将其从堆中取出,空间复杂度是O(n)
原地堆排序
直接在要排序数组中进行堆化操作,无需开辟新的空间,空间复杂度是O(1)
- 通过heapify过程将一个数组构建成最大堆,数组首元素就是最大堆中的最大值v
- 首元素与末尾元素交换,交换后最大值已经到达正确位置,下次排序不用再对其操作
此时橙色部分因首元素的存在而不再是最大堆,那么对首元素进行shiftDown操作,使之再次成为最大堆
- 针对最大堆重复操作1、2,直到全部变为蓝色
注意:由于整个排序过程在数组上进行,而通常数组是从0开始索引的
template<typename T>
void __shiftDown(T arr[],int n,int k){//k是进行下沉操作的索引
//1.左孩子不越界
while(2*k+1<n){
int j=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<typename T>
void heapSort(T arr[],int n){
//heapify操作:将arr数组构建成了一个堆
// 注意,此时我们的堆是从0开始索引的
// 从(最后一个元素的索引-1)/2开始
// 最后一个元素的索引 = n-1
for(int i=((n-1)-1)/2;i>=0;i--)
__shiftDown(arr,n,i);
for(int i=n-1;i>0;i--){
//将首元素与末尾元素交换
swap(arr[i],arr[0]);
//对首元素进行下沉操作
__shiftDown(arr,i,0); //每循环一次,未排序数组元素就少一个
}
}