数据结构——双端堆（C语言）

淡淡的烟草味﹌ 2022-08-25 14:54 166阅读 0赞

## 定义 ##

双端堆：是一棵完全二叉树，该完全二叉树要么为空，要么同时满足下列性质：

（1） 根节点不包含元素；

（2） 左子树是一个最小堆；

（3） 右子树是一个最大堆；

（4） 如果右子树不空，令i是左子树中任意一节点，j是i在右子树中的对应节点。如果i在右子树中的对应节点不存在，则令j为i父节点在右子树中的对应节点。对于节点i和j，节点i的关键字小于等于j的关键字。

![SouthEast][]

## 双端堆的插入操作 ##

步骤

（1）若插入的新元素是在最小堆，将新插入节点与其在最大堆中对应节点相比较，如果大于对应节点，则将两个节点元素互换，对最大堆执行max\_insert操作；否则，只需对最小堆执行min\_insert操作。

（2）若插入的新元素是在最大堆，将新插入节点与其在最小堆中对应节点相比较，如果小于对应节点，则将两个节点元素互换，对最小堆执行min\_insert操作；否则，只需对最大堆执行max\_insert操作。

## 双端堆的删除操作 ##

以下以删除最小元素为例，删除最大元素相似。

删除最小元素基本思想：

首先，将从最小堆的根节点删除的元素转换为从最小堆的叶子节点中删除元素的操作。这种转换是通过在沿根节点到叶子节点的路径上选择关键字值较小的节点逐步上移来完成的。其结果是把初始时位于最小堆根节点处的空位移到一个叶子节点p。然后，用初始时位于双端堆最后位置的元素temp插入到该叶子节点p。插入操作类似双端堆的插入操作，只是插入操作仅在最小堆中进行，且其中max\_paretner(i)的返回值j有改变。

## 程序 ##

函数声明：

#ifndef HEAP_H_INCLUDED
    #define HEAP_H_INCLUDED
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #include<math.h>
    #define MAX_SIZE 10
    int heap[MAX_SIZE];
    void deap_insert(int *heap,int *n,int item);//双端堆插入操作
    int delete_deap_min(int *heap,int *n);//删除双端堆的最小元素
    bool max_heap(int n);//判断节点是否在最大堆中
    int min_partner(int n);
    int max_partner(int n);
    void min_insert(int *heap,int n,int item);
    void max_insert(int *heap,int n,int item);
    void  modified_deap_insert(int *heap,int i,int temp,int n);
    int modified_max_partner(int i,int n);
    #endif // HEAP_H_INCLUDED

函数定义：

#include"Heap.h"
    /*双端堆的插入操作*/
    void deap_insert(int *heap,int *n,int item)
    {
        int i;
        (*n)++;
        if((*n)==MAX_SIZE)//满堆
        {
            printf("The heap is full.\n");
            exit(1);
        }
        if(2==(*n))//原来为空堆
            heap[2]=item;
        else
        {
            bool flag;
            flag=max_heap(*n);//插入的节点是否在最大堆
            switch(flag)
            {
            case true://节点在最大堆
                i=min_partner(*n);//插入节点在最小堆所对应的节点
                if(item<heap[i])//比较最小堆节点和插入元素的大小
                {
                    heap[*n]=heap[i];//交换元素
                    min_insert(heap,i,item);//把数据item插入到最小堆中
                }
                else
                    max_insert(heap,*n,item);//否则插入到最大堆中
                break;
    
            case false:
                     i=max_partner(*n);//插入节点在最大堆中对应的节点
                    if(item>heap[i])//比较最大堆节点和插入元素的大小
                        {
                            heap[*n]=heap[i];//交换元素
                            max_insert(heap,i,item);//插入到最大堆中
                        }
                    else
                        min_insert(heap,*n,item);//否则插入到最小堆
                    break;
            }
        }
    }
    /*删除双端堆的最小元素操作*/
    int delete_deap_min(int *heap,int *n)
    {
        int i,j;
        int temp;
        int item;
        if(*n<2)
        {
            fprintf(stderr,"The heap is empty.\n");
            exit(1);
        }
        item=heap[2];//要删除的元素
        temp=heap[(*n)--];//最后元素赋给temp;
        for(i=2;2*i<=*n;)
        {//将从最小堆根节点删除元素的操作
        //转换为从最小堆的叶子节点中删除元素的操作
            j=2*i;//j为i的叶子节点
            if(j+1<=*n)
            {
                if(heap[j]>heap[j+1])
                j++;//找出叶子节点中最小的关键字值节点
            }
            heap[i]=heap[j];//将叶子节点上移
            i=j;//其结果是把初始时位于根节点处的空位移动到叶子节点i;
        }
        modified_deap_insert(heap,i,temp,*n);//用初始时位于双端堆最后位置的节点元素插入到叶节点i;
        //该插入操作与deap_insert()的插入操作基本类似;只是插入操作仅在最小堆中;且其中max_partner(i)
        //的返回值j改变;
        return item;
    }
    /*判断节点n是否在最大堆中*/
    bool max_heap(int n)
    {
        double a = log(n)/log(2);
        double j = n + pow(2, (int)a-1);
        double b = log(j)/log(2);
        if((int)a == (int)b)
            return false;
        else
            return true;
    }
    /*返回最大堆节点n对应最小堆的结点*/
    int min_partner(int n)
    {
        double k = log(n)/log(2);
        double a = pow(2, (int)k-1);
        return n - (int)a;
    }
    /*返回最小堆节点n对应最大堆的结点*/
    int max_partner(int n)
    {
        double k = log(n)/log(2);
        double a = pow(2, (int)k-1);
        return (n + (int)a)/2;
    }
    /*最小堆的插入操作*/
    void min_insert(int *heap,int n,int item)
    {
        int i,parent;
        i=n++;
        parent=i/2;
        while(parent>=1)
        {
            if(heap[parent]>item)
            {
                heap[i]=heap[parent];
                i=parent;
                parent/=2;
            }
            else break;
        }
        heap[i]=item;
    }
    /*最大堆的插入操作*/
    void max_insert(int *heap,int n,int item)
    {
        int i,parent;
        i=n++;
        parent=i/2;
        while(parent>1)
        {
            if(heap[parent]<item)
            {
                heap[i]=heap[parent];
                i=parent;
                parent/=2;
            }
            else break;
        }
        heap[i]=item;
    }
    /*调整双端堆*/
    void  modified_deap_insert(int *heap,int i,int temp,int n)
    {
        int j;
        int item=temp;
        i++;
        if(i==MAX_SIZE)//满堆
        {
            printf("The heap is full.\n");
            exit(1);
        }
        if(2==i)//原来为空堆
            heap[2]=item;
        else
        {
            bool flag;
            flag=max_heap(i);//插入的节点是否在最大堆
            switch(flag)
            {
            case true://节点在最大堆
                j=min_partner(i);//插入节点在最小堆所对应的节点
                if(item<heap[j])//比较最小堆节点和插入元素的大小
                {
                    heap[i]=heap[j];//交换元素
                    min_insert(heap,j,item);//把数据item插入到最小堆中
                }
                else
                    max_insert(heap,i,item);//否则插入到最大堆中
                break;
    
            case false:
                     j=modified_max_partner(i,n);//插入节点在最大堆中对应的节点
                    if(item>heap[j])//比较最大堆节点和插入元素的大小
                        {
                            heap[i]=heap[j];//交换元素
                            max_insert(heap,j,item);//插入到最大堆中
                        }
                    else
                        min_insert(heap,i,item);//否则插入到最小堆
                    break;
            }
        }
    }
    int modified_max_partner(int i,int n)
    {
        double k = log(i)/log(2);
        double a = pow(2, (int)k-1);
        int j;
        j=(i + (int)a);
        if(j>n)
        return j/2;
        else return NULL;
    }

程序测试：

#include"Heap.h"
    
    int main()
    {
        int i,item;
        int n=1;
        for(i=2;i<MAX_SIZE;i++)
        {
            scanf("%d",&item);
            deap_insert(heap,&n,item);
        }
        for(i=2;i<=n;i++)
            printf("%d ",heap[i]);
        printf("\n");
        item=delete_deap_min(heap,&n);
        printf("The deleted data is:%d",item);
        printf("\n");
        for(i=2;i<=n;i++)
            printf("%d ",heap[i]);
        return 0;
    }

[SouthEast]: /images/20220824/1125109ac2ce4b3f987e8d693681071c.png