又见 “堆排序”

阳光穿透心脏的1/2处 2022-03-20 01:14 248阅读 0赞

以前每次遇到排序的时候，要使用高效的算法，总会想到堆，每次都没有总结，都要自己慢慢写，无语，现在总结一下，哎。。。。。方便以后，呵呵！~

基本概念：

大根堆：parent的权值大于lchild和rchild

小根堆：parent的权值小于lchild和rchild

其基本思想为(以小根堆为例)：

1)将初始待排序关键字序列(K1,K2....Kn)构建成小根堆，此堆为初始的无序区；

2)将堆顶元素K\[1\]与最后一个元素K\[n\]交换，此时得到新的无序区(K1,K2,......Kn-1)和新的有序区(K)，注意，此时K是最小的数已经得到！

3)由于交换后新的堆顶K\[1\]可能违反堆的性质，因此需要对当前无序区(K1,K2,......Kn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(K1,K2....Kn-2)和新的有序区(Kn-1,Kn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

>>> 对于具体的图示我相信任何一本书上都可以查到，这里主要是给出可行的算法实现，方便以后的编程！( 次算法在九度oj上通过 )

#include <stdio.h>
    
    void swap( int *data, int *b )   // 交换元素
    {
         int t = *data;
         *data = *b;
         *b = t;
    }
    
    void adjust_heap(int *data,int i,int n)  
    {
        int lc = 2 * i;       //左孩子节点序号 
        int rc = 2 * i + 1;   //右孩子节点序号 
        int min = i;          
        
        if( i <= n / 2 )      
        {
            if( lc <= n && data[lc] > data[min] )  // 此处改为lc <= n && data[lc] < data[min]就是大根堆 
            {
                min = lc;
            }    
            if( rc <= n && data[rc] > data[min] ) // 此处改为rc <= n && data[rc] < data[min]就是大根堆 
            {
                min = rc;
            }
            if( min != i )
            {
                swap(&data[i],&data[min]);
                adjust_heap(data,min,n); //避免调整之后以min为父节点的子树不是堆 
            }
        }        
    }
    
    void build_heap(int *data,int n)    
    {
        int i;
        
        for( i = n / 2; i >= 1; i-- ) //非叶节点最大序号值为n/2 
        {
            adjust_heap(data,i,n);    
        }    
    } 
    
    void sort_heap(int *data,int n) 
    {
        int i;
        
        for( i = n; i >= 1; i-- )
        {
            swap(&data[1],&data[i]);     //交换堆顶和最后一个元素
            adjust_heap(data,1,i-1);      //重新调整
        }
    } 
    
    int main(  )
    {
        int *data;
        int n,i;
    while( scanf("%d",&n) != EOF )
        {
            if( !n )
    		{
    			continue;
    		}
            
            data = ( int* )malloc( sizeof( int ) * (n + 1) );
            
            for( i = 1; i <= n; i++ )
            {
                scanf("%d", &data[i]);
            }
            
            build_heap(data,n);
            sort_heap(data,n);
            
            for( i = 1; i <= n; i++ )
            {
                printf("%d ", data[i]);
            }
            printf("\n");
        }
        return 0;
    }

`下面是选出最小的K个数的处理：`

// 小根堆( 堆是完全二叉树，所以用数组可以！ ) 
    
    #include <stdio.h>
    
    void swap( int *data, int *b )
    {
         int t = *data;
         *data = *b;
         *b = t;
    }
    
    void adjust_heap(int *data,int i,int n)  
    {
        int lc = 2 * i;       
        int rc = 2 * i + 1;   
        int min = i;             
        
        if( i <= n / 2 )      
        {
            if( lc <= n && data[lc] > data[min] )
            {
                min = lc;
            }    
            if( rc <= n && data[rc] > data[min] )
            {
                min = rc;
            }
            if( min != i )
            {
                swap(&data[i],&data[min]);
                adjust_heap(data,min,n); 
            }
        }        
    }
    
    void build_heap(int *data,int n)    
    {
        int i;
        
        for( i = n / 2; i >= 1; i-- ) 
        {
            adjust_heap(data,i,n);    
        }    
    } 
    
    void sort_heap(int *data,int n)   
    {
        int i;
        
        for( i = n; i >= 1; i-- )
        {
            swap(&data[1],&data[i]);             
            adjust_heap(data,1,i-1);     
        }
    } 
    
    int main(int argc, char *argv[])
    {
        int data[200000];
        int n, k;
        int i;
        while( scanf("%d%d",&n, &k) != EOF )
        {
            for( i = 1; i <= n; i++ )  // 注意此处从 idx = 1 开始 
            {
                scanf("%d", &data[i]);
            }
            
            build_heap(data,n);
            sort_heap(data,n);
            /*
            for( i = 1; i <= n; i++ )
            {
                printf("%d ", data[i]);
            }
            printf("\n");
            */
            while( k > 1 )   // 此处是核心
            {
                   k--;
                   printf("%d ", data[1]);
                   data[1] = data[n];
                   n--;
                   sort_heap(data,n);
            }
            printf("%d\n", data[1]);
        }
        return 0;
    }
     // 结束，呵呵~