堆排序和优先队列

目录

一：什么是堆

二：最大堆的代码实现 

 构造函数+析构函数

核心函数---入堆和出堆

构造函数之：用数组构造堆 

两种构造函数分别对应了两个堆排序 

完整程序 

原地堆排序

---

一：什么是堆

最大堆：

结构上是一颗完全二叉树

数值上要求：父节点的值>=其孩子节点的值

二：最大堆的代码实现 

因为堆是完全二叉树的结构，所以用动态数组去存储最大堆。

template<class Type>
class maxHeap{
private:
    Type* data;
    int maxSize;
    int curSize;
    void doublespace(){
        Type* tmp=data;
        maxSize*=2;
        data=new Type[maxSize];
        for(int i=1;i<=curSize;i++){
            data[i]=tmp[i];
        }
        delete[] tmp;
    }
};

 构造函数+析构函数

public:
    //构造函数
    maxHeap(int initsize=5){
        data=new Type[initsize+1];//堆从1开始存储
        maxSize=initsize;
        curSize=0;
    }
    //用数组构造
    template<typename T>
    maxHeap(T a[],int n);
    //析构函数
    ~maxHeap(){ delete[] data;}

核心函数---入堆和出堆

 入堆

//入堆
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(k;k>1 && data[k/2]<e;k/=2){//根节点之前
            data[k]=data[k/2];
     }
     data[k]=e;
}
template<class Type>
void maxHeap<Type>::enHeap(const Type& x){
     if(curSize==maxSize-1) doublespace();
     data[++curSize]=x;
     shiftUp(curSize);
}

思路：

把元素放入当前堆长度的后一个位置，然后为了维护堆的结构性，进行向上调整

注意----从1开始存储时，数组第k个位置的结点，其父节点k/2,其左孩子k*2,右孩子k*2+1

出堆 

//入堆
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(k;k>1 && data[k/2]<e;k/=2){//根节点之前
            data[k]=data[k/2];
     }
     data[k]=e;
}
template<class Type>
void maxHeap<Type>::enHeap(const Type& x){
     if(curSize==maxSize-1) doublespace();
     data[++curSize]=x;
     shiftUp(curSize);
}

堆是优先级队列，所以根节点出堆，然后把当前堆的最后一个结点放到根节点，数组长度-1，然后从根节点进行向下调整。

向下调整步骤：

• 循环前提：当前结点k至少有左孩子(k*2<=数组长度）
• 用j来记录左右孩子最大值：k的右孩子存在然后比较左右孩子数值取最大（if条件）
• 然后判断是否要调整：即---把左右孩子最大值和父节点判断，维护最大堆
• 更新k=j,然后继续循环

构造函数之：用数组构造堆 

//用数组构造
template<typename T>
    maxHeap(T a[],int n){
        //注意：成员变量初始化
        maxSize=n+1;
        curSize=n;
        data=new Type[maxSize];
        for(int i=1;i<=n;i++){
            data[i]=a[i-1];
        }
        //从最后一个非叶子结点，逐个向下调整
        for(int j=n/2;j>=1;j--){//根节点也要进行,堆为1
        shiftDown(j);
        }
    }

 思路：

把数组值依次存入堆数组，然后从第一个非叶子结点逐次遍历到根节点，每次都执行向下调整。注意：从1存放的堆的第一个非叶子结点是curSize/2

两种构造函数分别对应了两个堆排序 

template<typename T>
void heapSort_one(T a[],int n){
    maxHeap<int> heap;
    for(int i=0;i<n;i++){
        heap.enHeap(a[i]);
    }
    for(int i=n-1;i>=0;i--){
        a[i]=heap.deHeap();
    }
}

template<typename T>
void heapSort_arr(T a[],int n){
  maxHeap<int> heap(a,n);
  for(int i=n-1;i>=0;i--){
        a[i]=heap.deHeap();
    }
}

完整程序 

maxheap.h 

#ifndef my_Maxheap
#define my_Maxheap
template<class Type>
class maxHeap{
private:
    Type* data;
    int maxSize;
    int curSize;
    void doublespace(){
        Type* tmp=data;
        maxSize*=2;
        data=new Type[maxSize];
        for(int i=1;i<=curSize;i++){
            data[i]=tmp[i];
        }
        delete[] tmp;
    }
    //辅助函数---向上调整和向下调整
    void shiftUp(int k);
    void shiftDown(int k);
public:
    //构造函数
    maxHeap(int initsize=5){
        data=new Type[initsize+1];//堆从1开始存储
        maxSize=initsize;
        curSize=0;
    }
    template<typename T>
    maxHeap(T a[],int n){
        //注意：成员变量初始化
        maxSize=n+1;
        curSize=n;
        data=new Type[maxSize];
        for(int i=1;i<=n;i++){
            data[i]=a[i-1];
        }
        //从最后一个非叶子结点，逐个向下调整
        for(int j=n/2;j>=1;j--){//根节点也要进行,堆为1
        shiftDown(j);
        }
    }
    //析构函数
    ~maxHeap(){ delete[] data;}
    //核心函数：入堆和出堆
    void enHeap(const Type& x);//堆是优先队列，所以放置后面，向上调整
    Type deHeap();//根节点出堆，向下调整
};
//入堆
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(;k>1 && data[k/2]<e;k/=2){//根节点之前
            data[k]=data[k/2];
     }
     data[k]=e;
}
template<class Type>
void maxHeap<Type>::enHeap(const Type& x){
     if(curSize==maxSize-1) doublespace();
     data[++curSize]=x;
     shiftUp(curSize);
}
//出堆
template<class Type>
void maxHeap<Type>::shiftDown(int k){
     Type e=data[k];
     int j;
     while(k*2<=curSize){//左孩子存在
        j=k*2;
        if(j+1<=curSize && data[j+1]>data[j]) j+=1;//取左右孩子最大值
        //判断：根节点和max(左右孩子)
        if(data[j]> e)  data[k]=data[j];
        else break;
        //更新k值
        k=j;
     }
     data[k]=e;
}
template<class Type>
Type maxHeap<Type>::deHeap(){
      Type x=data[1];
      data[1]=data[curSize--];
      shiftDown(1);
      return x;
}
#endif

sortHelper.h 

#include<ctime>
#include<cassert>
#include<iostream>
#include"maxheap.h"
using namespace std;
namespace sortHelper{
//生成数组
template<typename T>
T* gen_ran_arr(int n,int L,int R){
    assert(L<=R);
    srand(time(NULL));
    T* arr=new T[n];
    for(int i=0;i<n;i++){
        arr[i]=rand()%(R-L)+1;
    }
    return arr;
}
//打印数组
template<typename T>
void arr_print(T a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
/*堆排序*/
template<typename T>
void heapSort_one(T a[],int n){
    maxHeap<int> heap;
    for(int i=0;i<n;i++){
        heap.enHeap(a[i]);
    }
    for(int i=n-1;i>=0;i--){
        a[i]=heap.deHeap();
    }
}
template<typename T>
void heapSort_arr(T a[],int n){
  maxHeap<int> heap(a,n);
  for(int i=n-1;i>=0;i--){
        a[i]=heap.deHeap();
    }
}
}

原地堆排序

原地堆排序-----直接在原数组进行堆排序，不额外申请空间，因而序号也是0开始

在0开始的数组中：

• 结点k的父节点（k-1)/2，左孩子：2*k+1,右孩子2*k+2
• n个结点的堆中最后一个非叶子结点：(n-1)/2

template<typename T>
void shiftDown_yuandi(T a[],int n,int k){
    T e=a[k];
    int j;
    while(k*2+1<n){
        j=k*2+1;
        if(j+1<n && a[j+1]>a[j]) j+=1;
        if(a[j]>e) a[k]=a[j];
        else break;
        k=j;
    }
    a[k]=e;
}
template<typename T>
void heapSort_yuandi(T a[],int n){
    //原数组先调整成堆
    for(int i=(n-1)/2;i>=0;i--){
        shiftDown_yuandi(a,n,i);
    }
    //把堆顶元素后移，依次再调整成堆
    for(int i=n-1;i>0;i--){
        swap(a[0],a[i]);
        shiftDown_yuandi(a,i,0);
    }
}

注意---不要讲j定义在while外