堆排序

heapSort

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

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

  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(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();

}

比较

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

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

原地堆排序

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

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

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

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

  3. 针对最大堆重复操作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); //每循环一次,未排序数组元素就少一个

    }

}


上一篇:SpringBoot开发案例之配置阿里巴巴Druid连接池


下一篇:MySQL之select语句