博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最大堆
阅读量:6445 次
发布时间:2019-06-23

本文共 3910 字,大约阅读时间需要 13 分钟。

1、最大堆的定义及其常用操作:

1 #include 
2 #include
3 4 #define true 1 5 #define false 0 6 #define ERROR -1 7 typedef int ElementType; 8 typedef int bool; 9 10 typedef struct HNode *Heap; /* 堆的类型定义 */11 struct HNode12 {13 ElementType *Data; /* 存储元素的数组 */14 int Size; /* 堆中当前元素的个数 */15 int Capacity; /* 堆的最大容量 */16 };17 18 typedef Heap MaxHeap; /* 堆的最大容量 */19 20 MaxHeap CreatHeap(int MaxSize); /* 创建空的最大堆,其最大长度为MaxSize */21 bool IsEmpty(MaxHeap H); /* 判断最大堆是否为空 */22 bool IsFull(MaxHeap H); /* 判断最大堆是否已满 */23 bool Insert(MaxHeap H, ElementType X); /* 插入成功返回true,否则返回false */24 ElementType DeleteMax(MaxHeap H); /* 删除并返回H中最大的元素 */

 

2、函数实现:

1 MaxHeap CreatHeap(int MaxSize) 2 { 3     MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode)); 4     H->Data = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType));   /* 数组起始单元为1,下标0没有存在堆中,是无用的,所以应该分配MaxSize+1个元素 */ 5     H->Size = 0; 6     H->Capacity = MaxSize; 7  8     return H; 9 }10 11 bool IsEmpty(MaxHeap H)12 {13     return H->Size == 0;14 }15 16 bool IsFull(MaxHeap H)17 {18     return H->Size == H->Capacity;19 }20 21 bool Insert(MaxHeap H, ElementType X)22 {23     if(IsFull(H))24     {25         printf("堆已满,插入失败!");26         return false;27     }28 29     ++H->Size;30     int i = H->Size;   /* i指向插入后堆中的最后一个元素的位置 */31 32     while(H->Data[i/2] < X && i > 1)  /*元素是从下标1开始存储的,所以i必须大于1 */33     {34         H->Data[i] = H->Data[i/2];  /* 上滤X */35         i = i/2;36     }37     H->Data[i] = X;     /* 将X插入到正确的位置 */38     return true;39 40 }41 42 ElementType DeleteMax(MaxHeap H)        /* 删除并返回H中最大的元素 */43 {44     if(IsEmpty(H))45     {46         printf("堆为空,删除失败!");47         return ERROR;48     }49     ElementType MaxItem, X;50     MaxItem = H->Data[1];51     X = H->Data[H->Size];    /* 取出删除前堆的最后一个元素 */52     --H->Size;53 54     int Parent, Child;55     for(Parent = 1; Parent*2 <= H->Size; Parent = Child)    /* 如果有儿子 */56     {57         Child = Parent * 2;58         if(Child != H->Size && H->Data[Child] < H->Data[Child+1])    /* 有右儿子, 且左儿子小于右儿子 */59             ++Child;      /* Child指向左右子节点的较大者 */60         if(H->Data[Child] > X)      61             H->Data[Parent] = H->Data[Child];    /* 下滤X */62         else63             break;     /* 子节点都比X小,则找到了X的插入位置,跳出循环 */64 65     }66     H->Data[Parent] = X;67 68     return MaxItem;69 }

 

 

3、最大堆的建立

目的:将已经存在的N个元素按照最大堆的要求存放在一个一维数组中。

 

方法1:通过插入操作,将N个元素一个个相继插入到一个初始为空的堆中去,其时间代价最大为O(NlogN)

方法2:在线性时间复杂度O(N)下建立最大堆。

  (1) 将N个元素按输入顺序存入,先满足完全二叉树的结构特性

  (2) 调整个节点位置,以满足最大堆的有序特性

 

方法2的时间复杂度分析:

从一个无序的完全二叉树进行节点向下过滤操作是构建最大堆的主要工作。某一节点向下过滤要与其下层的子孙节点比较键值,

因此最大的比较次数是树中各节点高度的和,这个高度和也就决定了算法的复杂度。而关于各节点的高度,我们有如下结论:

  一个高度为h的完全二叉树最多包含2^h - 1个节点(完美二叉树) , 这些节点的高度和为 2^h - 1 - h。 ( 证明过程见《数据结构与算法分析-C语言描述》P141.)

又由于一个完全二叉树的节点个数N是在2^(h-1) 和 2^h - 1之间,因此节点的高度和为O(N),说明最大堆建立算法的复杂度与节点个数呈线性关系。

 

用方法2构建最大堆的代码实现:

 

1 void PercDown(MaxHeap H, int p) 2 {  /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */ 3     int Parent, Child; 4     ElementType X; 5      6     X = H->Data[p];   /* 取出根节点存放的值 */ 7      8     for(Parent = p; Parent*2 <= H->Size; Parent = Child)    /* 如果有儿子 */ 9     {10         Child = Parent * 2;11         if(Child != H->Size && H->Data[Child] < H->Data[Child+1])    /* 有右儿子, 且左儿子小于右儿子 */12             ++Child;      /* Child指向左右子节点的较大者 */13         if(H->Data[Child] > X)      14             H->Data[Parent] = H->Data[Child];    /* 下滤X */15         else16             break;     /* 子节点都比X小,则找到了X的插入位置,跳出循环 */17 18     }19     H->Data[Parent] = X;20 }21 22 void BuildHeap(MaxHeap H)23 {   /* 调整H->Data[]中的元素,使满足最大堆的有序性 */24     /* 这里假设所有H->Size个元素都已经存在H->Data[]中 */25     26     int i;27     28     /* 从最后一个节点的父节点开始,到根节点1,逐个调节子树 */29     for(i = H->Size/2; i > 0; --i)30         PercDown(H, i);31     32 }

 

由于PercDown函数中的参数MaxHeap都必须是最大堆,所以BuildHeap必须从最后一个节点的父节点开始,逐渐把子树全部调整为最大堆。

转载于:https://www.cnblogs.com/FengZeng666/p/9785626.html

你可能感兴趣的文章
打开PowerDesigner/PDM文件时出现"cannot load the dbms"错误
查看>>
多总结多成长,少走弯路..
查看>>
再译《A *路径搜索入门》之流畅版??
查看>>
一直听说的比特币区块链
查看>>
Android开发笔记
查看>>
【iOS越狱开发】如何将应用打包成.ipa文件
查看>>
DB2 dpf 创建表空间
查看>>
Kafka集成SparkStreaming
查看>>
使用 Live Writer 在 oschina 上写博客(实用)
查看>>
安装Fedora 16之后的那些事(持续更新)
查看>>
基本算法:堆排序
查看>>
统计文件夹内文件名
查看>>
Golang中的正则表达式
查看>>
c++ 使用广度优先算法走迷宫并标记路径
查看>>
MySQL给查询结果添加一表表示行号或名次(2)
查看>>
fastjson的getString和org.json的getString的区别
查看>>
大型网站技术架构读书笔记
查看>>
Uliweb 0.2.3 发布,灵活易用的 Python Web 框架
查看>>
java多线程的状态及转换
查看>>
解决python安装模块时出现“Unable to find vcvarsall.bat”
查看>>