优先级队列

待我称王封你为后i 2021-12-16 10:25 378阅读 0赞

#include <iostream>
    using namespace std;
    
    int parent(int i)
    {
        
    return i/2;
    }
    
    int left(int i)
    {
        
    return 2*i;
    }
    
    int right(int i)
    {
        
    return 2*i+1;
    }
    
    void exchange(int &a,int &b)
    {
        
    int temp;
        temp=a;
        a=b;
        b=temp;
    }
    
    //但就算法来看，heap_size（堆的大小）设为全局变量也许会好一些
    void max_heapify(int *a,int i,int heap_size)
    {
        
    int l=left(i);
    int r=right(i);
    int largest;
    if (l<=heap_size&&a[l]>a[i])
        {
        
            largest=l;
        }
    else
        {
        
            largest=i;
        }
    if (r<=heap_size&&a[r]>a[largest])
        {
        
            largest=r;
        }
    if (largest!=i)
        {
        
            exchange(a[i],a[largest]);
            max_heapify(a,largest,heap_size);
        }
    
    }
    
    void build_max_heap(int *a,int heap_size)
    {
        
    for (int i=heap_size/2;i>=0;i--)
        {
        
            max_heapify(a,i,heap_size);
        }
    }
    
    int heap_maximum(int *a)
    {
        
    return a[0];
    }
    
    int heap_extract_max(int *a,int heap_size)
    {
        
    if (heap_size<0)
        {
        
            cout<<"heap_underflow"<<endl;
    return 0;
        }
    
    int Max=a[0];
        a[0]=a[heap_size];
        heap_size=heap_size-1;
        max_heapify(a,0,heap_size);
    return Max;
    }
    
    void heap_increase_key(int *a,int i,int key)
    {
        
    if (key<a[i])
        {
        
            cout<<"new key is small than current key"<<endl;
    return;
        }
    
        a[i]=key;
    while (i>0&&a[parent(i)]<a[i])
        {
        
            exchange(a[i],a[parent(i)]);
            i=parent(i);
        }
    }
    
    void max_heap_insert(int *a,int key,int heap_size)        
    {
        
        heap_size=heap_size+1;
        a=(int*)realloc(a,sizeof(int)*(heap_size+1));
        a[heap_size]=-10000;
        heap_increase_key(a,heap_size,key);
    }
    
    int main()
    {
        
    int b[]={
        4,1,3,2,16,30,10,14};
    int *a;
    int heap_size=sizeof(b)/sizeof(int)-1;
        a=(int*)malloc(sizeof(int)*(heap_size+1));
        memcpy(a,b,sizeof(int)*(heap_size+1));
    
        build_max_heap(a,heap_size);
        max_heap_insert(a,11,heap_size);
    
    for (int i=0;i<=heap_size+1;i++)
            cout<<a[i]<<"";
    
        cout<<endl;
        cout<<heap_maximum(a)<<endl;
        cout<<heap_extract_max(a,heap_size+1)<<endl;
    
    for (int i=0;i<=heap_size;i++)
            cout<<a[i]<<"";
    
        cout<<endl;
        system("pause");
        free(a);
    return 0;
    
    }

转载于:https://www.cnblogs.com/tiandsp/archive/2012/02/17/2356471.html