欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆(优先队列,最大堆的基本操作,堆的例题)

程序员文章站 2022-03-31 19:08:36
...

1、堆(优先队列):是一种特殊的“队列”,取出元素的顺序是
依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序。

2、堆的特性:
(1)结构性:用数组表示的完全二叉树(堆一定是完全二叉树);

(2)有序性:任一结点的关键字是其子树所有结点的最大值(或最小值)

“最大堆(MaxHeap)”,也称“大顶堆”:任一结点的关键字是其子树所有结点的最大值。
堆(优先队列,最大堆的基本操作,堆的例题)
“最小堆(MinHeap)”,也称“小顶堆” :任一结点的关键字是其子树所有结点的最小值。
堆(优先队列,最大堆的基本操作,堆的例题)

3、最大堆的基本操作:

!!!这里主要讲解最大堆,最小堆类似。这里的所有操作都是建立在以下标为1开始存储元素,下标为0的地方没有存储真实的元素
(1)、建立一个空的堆

#define MAXdata 10000
typedef struct Heap{
    int *a;
    int size;//当前元素个数 
    int maxsize;//最大存储量 
}heap;
heap* creat_maxheap(int maxdata,heap* h)//创建一个最大容量为maxdata的空堆 
{
    h->a = (int *)malloc((maxdata + 1)*sizeof(int));
    //因为堆中元素是从下标为1的地方开始存放的,所以maxsize+1 
    h->maxsize = maxdata;
    h->size = 0 ;
    h->a[0] = MAXdata;//定义哨兵为大于堆中所有元素的值 
    return h; 
}

(2)、判断一个堆是否满

int Isfull_maxheap(heap* h)//判断最大堆是否满 
{
    return h->maxsize == h->size;//若满则返回1,未满则返回0 
}

(3)、插入元素

void insert_maxheap(int x,heap* h)//向堆中插入一个元素 
{
    int i;
    if(Isfull_maxheap(h))
    {
        printf("最大堆已满!\n");
        return ;
    }
    i = ++h->size;//i指向插入后堆中的最后一个元素的位置
    for ( ; h->a[i/2] < x; i/=2 )
        h->a[i] = h->a[i/2]; //上滤X 
    h->a[i] = x; //将X插入 
    return ;
} 

(4)、判断堆是否为空

int Isempty_maxheap(heap* h)
{
    return h->Size == 0;//若空则返回1,不空则返回0 
}

(5)、删除堆中最大的元素并返回

int deletemax_heap(heap* h) 
// 从最大堆h中取出键值为最大的元素,并删除一个结点 
{
    int parent,child;
    int maxdata,temp;
    if(Isempty_maxheap(h))
    {
        printf("最大堆以为空!\n");
        return 0;
    } 
    maxdata = h->a[1];//取出根结点最大值 
    //用最大堆中最后一个元素从根结点开始向上过滤下层结点
    temp = h->a[h->size--];
    //最开始用最后一个结点代替根结点,再交换顺序使之成为堆 
    for(parent = 1;parent*2 <= h->size;parent = child)
    {
        child = parent*2;
        if((child != h->size) && (h->a[child] < h->a[child+1]))
        {
            child++;//child指向左右子结点的较大者
        }
        if(temp >= h->a[child])
        break;
        else
        h->a[parent] = h->a[child];//移动temp元素到下一层
    }
    h->a[parent] = temp;
    return maxdata;
}

(6)、简单例题:将数组存放为最大堆,再遍历输出,删除最大元素后再遍历删除后的结果

#include <stdio.h>
#include <stdlib.h> 
#include <math.h>
#define MAXdata 10000
typedef struct Heap{
    int *a;
    int size;//当前元素个数 
    int maxsize;//最大存储量 
}heap;
heap* creat_maxheap(int maxdata,heap* h)//创建一个最大容量为maxdata的空堆 
{
    h->a = (int *)malloc((maxdata + 1)*sizeof(int));
    //因为堆中元素是从下标为1的地方开始存放的,所以maxsize+1 
    h->maxsize = maxdata;
    h->size = 0 ;
    h->a[0] = MAXdata;//定义哨兵为大于堆中所有元素的值 
    return h; 
}
int Isfull_maxheap(heap* h)//判断最大堆是否满 
{
    return h->maxsize == h->size;//若满则返回1,未满则返回0 
}
void insert_maxheap(int x,heap* h)//向堆中插入一个元素 
{
    int i;
    if(Isfull_maxheap(h))
    {
        printf("最大堆已满!\n");
        return ;
    }
    i = ++h->size;//i指向插入后堆中的最后一个元素的位置
    for ( ; h->a[i/2] < x; i/=2 )
        h->a[i] = h->a[i/2]; //上滤X 
    h->a[i] = x; //将X插入 
    return ;
} 
int Isempty_maxheap(heap* h)
{
    return h->size == 0;//若空则返回1,不空则返回0 
}

int deletemax_heap(heap* h) 
// 从最大堆h中取出键值为最大的元素,并删除一个结点 
{
    int parent,child;
    int maxdata,temp;
    if(Isempty_maxheap(h))
    {
        printf("最大堆以为空!\n");
        return 0;
    } 
    maxdata = h->a[1];//取出根结点最大值 
    //用最大堆中最后一个元素从根结点开始向上过滤下层结点
    temp = h->a[h->size--];
    //最开始用最后一个结点代替根结点,再交换顺序使之成为堆 
    for(parent = 1;parent*2 <= h->size;parent = child)
    {
        child = parent*2;
        if((child != h->size) && (h->a[child] < h->a[child+1]))
        {
            child++;//child指向左右子结点的较大者
        }
        if(temp >= h->a[child])
        break;
        else
        h->a[parent] = h->a[child];//移动temp元素到下一层
    }
    h->a[parent] = temp;
    return maxdata;
}
void print_maxheap(heap* h)
{
    int i;
    for (i=1; i<h->size+1; i++)
        printf("%d ", h->a[i]);
}
int main()
{
    int a[5] = {50,10,70,90,30};
    int i,len = 5;
    heap* h = (heap*)malloc(sizeof(heap));
    h = creat_maxheap(len,h);
    printf("依次添加:"); 
    for(i = 0;i<len;i++)
    {
        printf("%d ",a[i]);
        insert_maxheap(a[i],h);
    } 
    printf("\n最大堆:"); 
    print_maxheap(h);
    printf("\n删除的元素:%d",deletemax_heap(h));
    printf("\n删除元素后的最大推:");
    print_maxheap(h); 
} 

运行结果:
堆(优先队列,最大堆的基本操作,堆的例题)