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); //每循环一次，未排序数组元素就少一个
}
}