【数据结构】筛选法建堆

我就是我 2022-06-14 20:50 197阅读 0赞

如果已经存在N个数据元素，如何将这些元素按照堆的要求存储在一个一维数组中呢？这就是堆的建立问题。  
首先我们可以想到按照之前的堆的插入算法将这N个元素依次插入一个空堆中，分析时间复杂度，每插入一个元素最多要进行logN（即堆的深度）次比较，所以对于N个元素用插入法建堆的时间复杂度是O(NlogN)。  
这里要介绍的是筛选法建堆，它可以在线性时间复杂度下完成建堆。以最大堆为例介绍具体操作过程：

1.  首先将N个数据元素存入一个一维数组，并把这个数组视作一棵完全二叉树。
2.  从二叉树的最后一个非叶结点开始用从上向下过滤的方法调整以该非叶结点为根节点的二叉树为最大堆。
3.  对前面的结点依次执行2的操作直到根结点执行完成为止。此时这棵二叉树就调整为了一个最大堆。
    
    注：从上向下过滤是指从二叉树的根结点开始，比较根结点和它的子结点，如果根结点比子结点中最大的那个小的话，就交换父节点和子结点的值，之后对以之前子结点为根节点的二叉树重复执行上述操作。

图解（图片非原创，侵删）  
![201107261321543165.png][]

下面是代码实现

typedef struct heap{
        int *Elements;//存放堆元素的数组
        //Elements[0]中存放一个大于堆中所有可能元素的哨兵，
        //所以堆顶位置在Elements[1]处
    
        int Size;//堆的当前元素个数
        int Capacity;//堆的最大容量
    }* MaxHeap;
    
    void BuildMaxHeap(MaxHeap H)
    {
        int parent,child,temp;
        for(int i = H->Size/2; i>0; i--){
            parent = i;
            temp = H->Elements[i];
            while(parent*2<=H->Size){
                child = parent*2;
                if((child!=H->Size)&&(H->Elements[child]<H->Elements[child+1]))
                    child++;
                if(temp<H->Elements[child]){
                    H->Elements[parent] = H->Elements[child];
                    parent = child;
                }
                else
                    break;
            }
            H->Elements[parent] = temp;
        }
        printf("%d\n",H->Size);
    }

[201107261321543165.png]: /images/20220615/32e267b963174a94a53bb26c3a7f7f11.png