堆--LogN的数据结构

﹏ヽ暗。殇╰゛Y 2023-06-04 04:59 87阅读 0赞

我们这里的堆是指用来表示元素集合的一种数据结构

![261007463877076.jpg][]

一个二叉树是一个堆是由堆的两个性质决定的（以小根堆为例）

1：任何节点的值都小于或等于其子节点的值

2：该二叉树最多在两层上具有叶节点，其中最底层的叶节点尽可能的靠左分布

我们可以从数学上约束这两个性质

x\[i/2\]<=x\[i\](2<=i<=n)

从这个性质我们可以定义heap(l,u):x\[i/2\]<=x\[i\](2l<=i<=u)

下面我们考虑两种情况：

1：当x\[1,...n-1\]是堆时，在x\[n\]中放置一个任何的元素可能无法产生heap(1,n)

2：当x\[1...n\]是一个堆时，给x\[1\]分配一个新值得到heap(2,n)，如何得到heap(1,n)

现在我们来探讨这两个问题：

![261104184027297.png][]

x\[n\]即为图中带圈的元素，该元素一直往上与父节点交换，知道该节点的值大于等于其父节点（或者位于树根）为止

如果过程中heap(1,n-1)为真，那么heap(1,n)为真

void siftup(int n)//sift 筛选
    {
        int i=n;
        while(true) {
            if(i==1) break;
            int p=i/2;
            if(x[p]<=x[i]) break;
            swap(i,p);
            i=p;
        }
    }

![261120149337371.png][]

x\[1\]即为图中带圈的元素，x\[1\]向下筛选，直到它没有子节点或者小于等于它的子节点

void siftdown(int n)
    {
        int i=1;
        while(true) {
            int c=2*i;
            if(c>n) break;//no child node
            if(c+1<=n)//c+1 is the right child,c+1<=n,i has right child
                if(x[c+1]<x[c]) c++;//select lesser one
            //c is the lesser child
            if(x[i]<=x[c]) break;
            swap(c,p);
            i=c;
        }
    }

通过解决这两个问题，我们实现了给堆增加一个元素或者删除最小的元素（最小堆）

现在我们考虑用堆的这两个操作来实现另一个数据结构--优先级队列

优先级队列（priority queue） 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素 （3）删除

一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。

如果用我们上面讨论的最小堆来实现的话，那么对应的操作如下：

查找：返回x\[1\]

插入：插入新元素是将n+1，然后将新元素放在x\[n\]处，这样我们就具备了调用siftup的前提：heap(1,n-1)

删除：由于是最小堆，x\[1\]即为优先权最高的元素，删除x\[1\]，我们可以将x\[n\]移动到x\[1\]并将n-1，这样集合中的元素都在x\[1..n\]中了，并且heap(2,n)为真，那我们就可以调用siftdown了

template<class T>
    class priqueue
    {
    private:
        int n,maxsize;
        T *x;
        void swap(int i,int j){ T t = x[i];x[i]=x[j];x[j]=t;}
    public:
        priqueue(int m)
        {
            maxsize=m;
            x= new int[maxsize+1];
            n=0;
        }
        void insert(T t)
        {
            int i,p;
            x[++n]=t;
            for(i=n;i>1 && x[p=i/2]>x[i];i=p) swap(i,p);
        }
        T extractmin()
        {
            int i,c;
            T t = x[1];
            x[1]=x[n--];
            for(i=1;(c=2*i)<=n;i=c)
            {
                if(c+1<=n&&x[c+1]<x[c])
                    c++;
                if(x[i]<=x[c]) break;
                swap(i,c);
            }
            return t;
        }
        ~priqueue();
        
    };

优先级队列的实现为我们提供了一种简单的向量排序算法：首先在优先级队列中依次插入每个元素，然后排序删除它们

然而这种想法需要额外的一个数组的内存，但我们分析可知，是可以在一个数组上操作的，想法如下：

第一阶段：在原数组上建立堆，

第二阶段：使用堆来建立有序序列，由于x\[1\]是最小的元素，交换x\[1\]和x\[n--\]，然后把新的顶部元素向下筛选来重新获得堆性质，循环。

不过这样得到的是一个降序的有序序列，如果要得到升序的有序序列，我们要使用最大堆而不是最小堆

下面是实现的最小堆排序的代码：

#include <iostream>
    #include "stdlib.h"
    #include "time.h"
    using namespace std;
    int x[101]= {
        0};
    int co=0;
    void swap(int f,int s)
    {
        int temp=x[f];x[f]=x[s];x[s]=temp;
        co++;
    }
    void siftup(int n)//sift 筛选
    {
        int i=n;
        while(true) 
        {
            if(i==1) break;
            int p=i/2;
            if(x[p]<=x[i]) break;
            swap(i,p);
            i=p;
        }
    }
    void siftdown(int n)
    {
        int i=1;
        while(true) {
            int c=2*i;
            if(c>n) break;//no child node
            if(c+1<=n)//c+1 is the right child,c+1<=n,i has right child
                if(x[c+1]<x[c]) c++;//select lesser one
            //c is the lesser child
            if(x[i]<=x[c]) break;
            swap(c,i);
            i=c;
        }
    }
    int main(int argc, char const *argv[])
    {
        srand(unsigned(time(NULL)));
        for(int i=1;i<101;i++) 
        {
            x[i]=rand()%100;
            cout<<x[i]<<" ";
        }
        cout<<endl;
        //sort
        for(int i=2;i<=100;i++) siftup(i);
        for(int i=100;i>=2;i--)
        {
            swap(i,1);
            siftdown(i-1);
        }
        for(int i=1;i<101;i++) 
        {
            cout<<x[i]<<" ";
        }
        cout<<endl<<co;
        return 0;
    }

转载于:https://www.cnblogs.com/qwj-sysu/p/4051810.html

[261007463877076.jpg]: /images/20230601/604518a491d342e99833f2aaa050dea2.png
[261104184027297.png]: /images/20230601/26a062ce0d2b468d89997907c3384261.png
[261120149337371.png]: /images/20230601/2dc5f9039c3d4052a199ac6f6a14fdc9.png