Heap sort and priority queue

Catalog

One ： What is a heap

Two ： Code implementation of the largest heap  

  Constructors + Destructor

Core function --- Stacking in and out

Constructor ： Use arrays to construct heaps  

The two constructors correspond to two heap sorts  

The whole program  

Sort in place

---

One ： What is a heap

The biggest pile ：

Structurally, it is a Perfect binary tree

Numerical requirements ： The value of the parent node >= The value of its child node

Two ： Code implementation of the largest heap  

Because the heap is a complete binary tree structure , So use The dynamic array To store the largest heap .

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;
    }
};

  Constructors + Destructor

public:
    // Constructors 
    maxHeap(int initsize=5){
        data=new Type[initsize+1];// Heap from 1 Start storage 
        maxSize=initsize;
        curSize=0;
    }
    // Construct with array 
    template<typename T>
    maxHeap(T a[],int n);
    // Destructor 
    ~maxHeap(){ delete[] data;}

Core function --- Stacking in and out

  Into the heap

// Into the heap 
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(k;k>1 && data[k/2]<e;k/=2){// Before the root node 
            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);
}

Ideas ：

Put the element in the next position of the current heap length , And then for Maintain the structure of the heap , Conduct Adjust up

Be careful ---- from 1 When starting storage , Array number k Nodes at two locations , Its parent node k/2, Its left child k*2, The right child k*2+1

Out of pile  

// Into the heap 
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(k;k>1 && data[k/2]<e;k/=2){// Before the root node 
            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);
}

The heap is a priority queue , therefore The root node is out of the heap , Then put the current stack The last node is placed on the root node , The length of the array -1, Then adjust downward from the root node .

Adjust the step down ：

• Cyclic premise ： The current node k At least there are left children (k*2<= The length of the array ）
• use j To record the maximum value of left and right children ：k The right child of exists, and then compare the values of the left and right children to get the maximum （if Conditions ）
• Then decide whether to adjust ： namely --- Judge the maximum value of the left and right children and the parent node , Maintenance of maximum reactor
• to update k=j, And then the cycle goes on

Constructor ： Use arrays to construct heaps  

// Construct with array 
template<typename T>
    maxHeap(T a[],int n){
        // Be careful ： Initialization of member variables 
        maxSize=n+1;
        curSize=n;
        data=new Type[maxSize];
        for(int i=1;i<=n;i++){
            data[i]=a[i-1];
        }
        // From the last non leaf node , Adjust downward one by one 
        for(int j=n/2;j>=1;j--){// The root node should also be , Heap as 1
        shiftDown(j);
        }
    }

  Ideas ：

Store the array values into the heap array in turn , Then traverse from the first non leaf node to the root node , Perform downward adjustment every time . Be careful ： from 1 The first non leaf node of the stored heap is curSize/2

The two constructors correspond to two heap sorts  

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

The whole program  

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;
    }
    // Auxiliary function --- Adjust up and down 
    void shiftUp(int k);
    void shiftDown(int k);
public:
    // Constructors 
    maxHeap(int initsize=5){
        data=new Type[initsize+1];// Heap from 1 Start storage 
        maxSize=initsize;
        curSize=0;
    }
    template<typename T>
    maxHeap(T a[],int n){
        // Be careful ： Initialization of member variables 
        maxSize=n+1;
        curSize=n;
        data=new Type[maxSize];
        for(int i=1;i<=n;i++){
            data[i]=a[i-1];
        }
        // From the last non leaf node , Adjust downward one by one 
        for(int j=n/2;j>=1;j--){// The root node should also be , Heap as 1
        shiftDown(j);
        }
    }
    // Destructor 
    ~maxHeap(){ delete[] data;}
    // Core function ： Stacking in and out 
    void enHeap(const Type& x);// Heap is a priority queue , So put it in the back , Adjust up 
    Type deHeap();// The root node is out of the heap , Downward adjustments 
};
// Into the heap 
template<class Type>
void maxHeap<Type>::shiftUp(int k){
     Type e=data[k];
     for(;k>1 && data[k/2]<e;k/=2){// Before the root node 
            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);
}
// Out of pile 
template<class Type>
void maxHeap<Type>::shiftDown(int k){
     Type e=data[k];
     int j;
     while(k*2<=curSize){// Left child exists 
        j=k*2;
        if(j+1<=curSize && data[j+1]>data[j]) j+=1;// Take the maximum value of left and right children 
        // Judge ： Root node and max( Left and right children )
        if(data[j]> e)  data[k]=data[j];
        else break;
        // to update k value 
        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{
// Generating arrays 
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;
}
// Print array 
template<typename T>
void arr_print(T a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
/* Heap sort */
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();
    }
}
}

Sort in place

Sort in place ----- Directly sort the heap in the original array , No additional space required , Therefore, the serial number is also 0 Start

stay 0 In the starting array ：

• node k Parent node （k-1)/2, Left the child ：2*k+1, The right child 2*k+2
• n The last non leaf node in the heap of nodes ：(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){
    // The original array is first adjusted into a heap 
    for(int i=(n-1)/2;i>=0;i--){
        shiftDown_yuandi(a,n,i);
    }
    // Move the top element back , Then adjust it into piles 
    for(int i=n-1;i>0;i--){
        swap(a[0],a[i]);
        shiftDown_yuandi(a,i,0);
    }
}

Be careful --- Don't talk about j It's defined in while Outside