数据结构——最大堆和最小堆（C语言）

向右看齐 2022-08-25 14:49 218阅读 0赞

## 定义： ##

最大堆和最小堆都是一棵完全二叉树。

最大堆：是指根节点的关键字值是堆中的最大关键字值，且每个节点若有儿子节点，其关键字值都不小于其儿子节点的关键字值。

最小堆：是指根节点的关键字值是堆中的最小关键字值，且每个节点若有儿子节点，其关键字值都不大于其儿子节点的关键字值。

以下的操作以最大堆为例，最小堆相似。

![SouthEast][]

## 最大堆的插入操作 ##

步骤：

1.  把待增加的节点编号 i 设置为已知堆的总节点数加 1 即 i=++(\*n)，因此，新增的元素放在最下一层作为新的叶子节点。求出节点 i 的父节点 parent=i/2; 判断是否为空堆，并比较所插入元素与父节点关键字值的大小；
2.  若所插入节点关键字值大于父节点关键字值即item>heap\[parent\],则把父节点向下移,并把父节点作为当前节点，依次求父节点，即依次沿着树枝向上延伸直到根节点；
3.  把元素item插入到正确位置；

## 最大堆的删除操作 ##

最大堆的删除，即删除最大的元素。我们先取最后的元素提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置。

首先删除根节点，并把最后一个节点临时作为新的根节点，将新的根节点作为当前节点与其孩子节点中最大的关键值节点进行比较，若小于其孩子节点的关键值，则与其孩子节点进行交换位置，并把新位置作为当前节点继续与其孩子节点进行比较，一直延伸下去，直到没有孩子节点为止；

## 源程序 ##

函数声明：

#ifndef HEAP_H_INCLUDED
    #define HEAP_H_INCLUDED
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX_SIZE 10
    int heap[MAX_SIZE];
    void max_Heap_insert(int *heap,int *n,int item);
    int max_Heap_delete(int *heap,int *n);
    #endif // HEAP_H_INCLUDED

函数的定义：

#include"heap.h"
    
    /*最大堆的插入操作*/
    /*注：堆的下标是从1开始,而不是0*/
    void max_Heap_insert(int *heap,int *n,int item)
    {
        int i,parent;//i为当前节点,parent为i的父节点
        if((*n)==MAX_SIZE)//堆为满
        {
            printf("The heap is full\n");
            exit(1);
        }
        i=++(*n);
        parent=i/2;
        while((i!=1) && (item>heap[parent]))//若堆为非空,且所插入数据item大于父节点的关键字值
        {
            heap[i]=heap[parent];//父节点关键字值下移
            i=parent;//把父节点作为当前节点
            parent/=2;//依次求父节点
        }
        heap[i]=item;//插入到正确的位置
    }
    /*最大堆的删除操作*/
    int max_Heap_delete(int *heap,int *n)
    {
        int item,temp;
        int child,parent;
        if(*n==0)//若为空堆
        {
            printf("The heap is empty.\n");
            exit(1);
        }
        item=heap[1];//把最大堆的最大元素赋给item
        temp=heap[(*n)--];//堆的最后节点关键字值
        parent=1;
        child=2*parent;
        while(child<=(*n))
        {
            if(child<*n && heap[child]<heap[child+1])
                child++;//找出堆中最大关键字值的节点
            if(temp>=heap[child])break;//把最大节点关键字值与最后节点关键字值比较
            else
            {//若堆中存在比最后节点关键字值大的节点,则交换位置
                heap[parent]=heap[child];
                parent=child;
                child*=2;
            }
        }
        heap[parent]=temp;//插入到正确位置
        return item;//返回删除的关键字值
    }

程序测试：

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

[SouthEast]: /images/20220824/e78ef781341d4f9ab1335c3ecb7a0a4a.png