堆排序与优先队列

喜欢ヅ旅行 2022-03-24 16:10 296阅读 0赞

#include <iostream> 
    using namespace std; 
    int data[10]={71,18,151,138,160 ,63 ,174, 169 ,79 ,78 };
    void max_heapify(int data[],int i,int heapsize)
    { 
      int l=2*i+1; 
      int r=2*i+2; 
      int largest=i; 
      if(l<heapsize&&data[l]>data[i])
      { largest=l;} 
      if(r<heapsize&&data[r]>data[largest])
      {largest=r;} 
      if(largest!=i)
      { 
    	  int temp=data[largest];
          data[largest]=data[i];
          data[i]=temp;
          max_heapify(data,largest,heapsize);
      }
    } 
    void bulid_max_heap(int data[],int heapsize)
    {
        for(int i=heapsize/2-1;i>=0;i--)
    	max_heapify(data,i,heapsize);
    } 
    void heap_sort(int data[],int heapsize)
    {
    
       bulid_max_heap(data,heapsize); 
       for(int i=heapsize-1;i>0;i--)
      {
    	int t=data[0];
    	data[0]=data[i];
    	data[i]=t;
    	max_heapify(data,0,i); 
    
      }
    } 
    int main()
    { 
       cout<<"堆排序算法实现"<<endl;
       cout<<"排序之前的数据：";
       for(int i=0;i<10;i++)
       cout<<data[i]<<" ";
       cout<<endl;
       heap_sort(data,10);
       cout<<"排序之后的数据："; 
       for(int i=0;i<10;i++)
       cout<<data[i]<<" ";cout<<endl; 
       return 0;
    }

优先队列

#include <iostream> 
    using namespace std; 
    
    void max_heapify(int data[],int i,int heapsize)
    { 
    int l=2*i+1; 
    int r=2*i+2; 
    int largest=i; 
    if(l<heapsize&&data[l]>data[i])
    {largest=l;} 
    if(r<heapsize&&data[r]>data[largest])
    {largest=r;} 
    if(largest!=i)
    { int temp=data[largest];
    data[largest]=data[i];
    data[i]=temp;
    max_heapify(data,largest,heapsize);
    }
    } 
    
    void bulid_max_heap(int data[],int heapsize)//建堆的过程，通过自底向上地调用max_heapify来将一个数组data【1……n】变成一个大顶堆，
    {
        for(int i=heapsize/2-1;i>=0;i--)
    	max_heapify(data,i,heapsize);
    } 
    void heap_increase_key(int data[],int i,int key)
    {
    	data[i]=key;
        int j=(i-1)/2;
    	if(i>=1&&data[j]<data[i])
    	{
    		int temp=data[j];
            data[j]=data[i];
            data[i]=temp;
    		heap_increase_key(data,j,key);
    	}
    }
    void max_heap_insert(int data[],int key,int heapsize)
    {
    	heapsize=heapsize+1;
    	data[heapsize-1]=1;
    	heap_increase_key(data,heapsize-1,15);
    }
    void main()
    {  
    	int i=0,k=0;
    	int data[]={7,9,2,4,6,1,8,10};
    	bulid_max_heap(data,5);
    	while(i<5)
    		cout<<data[i++]<<endl;;
    	max_heap_insert(data,15,5);
    	i=0;
    	while(i<6)
    		cout<<data[i++]<<' ';
    }