赞
踩
复习堆基本操作的C语言实现,以小顶堆为例。
二叉排序树
若左子树不为空,左子树的所有结点的值均小于根的值;
若右子树不为空,右子树的所有结点均大于根的值;
它的左右子树也分别为二叉排序树。
二叉排序树进行中序排序就能得到一个有序序列。
堆
堆有不同的种类,但是我们在算法学习中,主要用的还是二叉堆
二叉堆有最大堆和最小堆之分。
大顶堆和小顶堆没有限制其左右子节点的大小关系。
堆的任意子树还是堆,大顶堆的子树也是大顶堆,小顶堆的子树仍是小顶堆
二叉排序树和堆的区别
[1] 最大最小节点:
[2] 深度:
[3] 数据查找的时间复杂度:
二叉堆的创建
二叉堆的实现:一般都通过“数组”来实现。不使用链表/指针来表示,因为二叉堆是完全二叉树的原因,用数组实现更简单,而且不存在大量的空间浪费
数组实现的二叉堆,父子节点之间存在着一定的关系。假设第一个元素索引0的话,则
索引为i的左孩子的索引为 2 * i + 1
索引为i的右孩子的索引为 2 * i + 2
索引为i的父节点的索引为 floor (( i - 1) / 2)
//定义堆结构体
typedef struct binary_heap
{
int *binHeap; //定义指向动态数组空间的指针
int maxSize; //保存数组的最大长度
int len; //保存堆长度的变量
}BinaryHeap,*BinHeap;
void InitHeap(BinHeap BP, int HeapSize)
{
if ( BP->binHeap = (BinHeap)malloc(sizeof(int) * HeapSize) == NULL)
{
printf("内存分配失败\n");
exit(1);
}
BP->maxSize = HeapSize;
BP->len = 0;
}
int CheckBinHeap(BinHeap BP)
{
if (BP->maxSize == 0)
return 1;
else
return 0;
}
void ClearBinHeap(BinHeap BP)
{
if (BP != NULL)
{
free(BP->binHeap);
BP->MaxSize = 0;
BP->len = 0;
}
}
二叉堆的元素插入/二叉堆生成
习惯将二叉堆画成树的形式,但本质上还是用数组实现。
在数组末尾加入这个元素,然后把这个元素往上挪,直到挪不动,经过了这种复杂度为Ο(logn)的操作,二叉堆性质没有变化
【小顶堆元素插入:利用最小堆的向上调整算法,如图所示】
//单个元素插入
void InsertHeap(BinHeap BP, int ele)
{
//如果堆满,将堆扩展为原两倍
if (BP->len == BP->maxSize)
{
BP->binHeap = (int *)realloc(BP->binHeap, 2*BP->maxSize*sizeof(int));
BP->maxSize = 2*BP->maxSize;
}
//队尾添加新元素
BP->binHeap[BP->len] = ele;
BP->len++;
int i = BP->len - 1; //i指向待调整元素的位置
/* 最小堆向上调整算法 */
while (i != 0) //首元素在位置0
{
int j = (i - 1) / 2;
if (ele >= BP->binHeap) //小顶堆,若堆元素大于待调整元素的双亲,则调整结束,跳出循环
break;
BP->binHeap[i] = BP->binHeap[j];
i = j; //将双亲移至待调整元素的位置
}
//将新元素调整至最终位置
BP->binHeap[i] = ele;
}
/* 二叉堆生成: 依次添加 */
for (int i = 0; i < dataNum; i++)
{
InsertHeap(BP, arr[i]);
}
二叉堆的删除-删除堆顶元素
【利用最小堆的向下调整算法,如图所示】
大顶堆,类似,大的元素往后判断
void DeleteHeap(BinHeap BP)
{
if (BP->len == 0)
{
printf("堆已空,退出运行\n");
exit(0);
}
int temp = BP->binHeap[0]; //取出堆顶元素
BP->len--;
if (BP->len == 0) //元素取出后判断
exit(1);
int lastData = BP->binHeap[BP->len]; //删除了一个元素,最后一个元素位置需要做调整
int i,j;
i = 0;
j = 2 * i + 1; //j指向i的左孩子的位置
/* 最小堆的向下调整算法 */
while (j <= BP->len - 1)
{
if (j < BP->len && BP->binHeap[j] > BP->binHeap[j + 1])
j++; //定位到较小值:小顶堆,顶点不大于子节点
if (lastData <= BP->binHeap[j]) //如果最后一个元素小于其子节点,说明找到了合适的位置,退出
break;
BP->binHeap[i] = BP->binHeap[j]; //将孩子元素移至父节点位置
i = j; //j的位置空,依次往后判断
j = 2 * i + 1;
}
BP->binHeap[i] = lastData;
}
二叉堆的删除-删除指定元素
【利用最小堆的向下调整算法,这里给出更一般的方法,包括删除堆顶元素】
步骤:
/* 查找元素位置 */
int GetIndex(BinHeap BP, int data)
{
int i;
for (i = 0; i < BP->maxSize; i++)
{
if (BP->binHeap[i] == data)
return i;
}
return -1;
}
//元素删除函数
bool RemoveHeap(BinHeap BP, int data)
{
int index;
if (BP->len == 0)
return false;
index = GetIndex(BP, data);
if (index == -1)
return false;
int temp = BP->binHeap[index]; //要删除元素,可不记录
int lastData = BP->binHeap[BP->len - 1]; //最后一个元素
BP->len--;
int i, j;
i = index; //为0为堆顶元素,这里是更一般的情况
j = 2 * i + 1;
/* 最小堆的向下调整算法 */
while (j <= BP->len - 1)
{
if (j < BP->len && BP->binHeap[j] > BP->binHeap[j + 1]) //定位到较小值;大顶堆则定位到较大值
j++;
if (lastData <= BP->binHeap[j]) //满足小顶堆定义,找到了合适位置
break;
//否则,调整节点位置
BP->binHeap[i] = BP->binHeap[j];
i = j;
j = 2 * i + 1;
}
BP->binHeap[i] = lastData;
return true;
}
函数参数
ptr:指向先前用malloc、calloc和realloc函数分配后的内存指针
new_size:内存块的新大小,可能大于也可能小于
函数说明
当扩展内存的时候,不会对添加进内存块的字节进行初始化
若不能调整内存则返回NULL,但原有内存中的数据是不会发生改变的
若第一个参数为NULL那么功能等同与malloc()函数,若第二个参数为0,那么会释放调用内存块,等同于free()函数
当缩小或者扩大内存时,一般不会对其进行移动,若无法扩大内存块,那么会在别处分配新的内存快,然后把旧内存块的数据复制到新块中,并将旧块删除释放内存
如果扩大内存,之前的数据不会被修改
【1】 realloc(NULL,10*size(int)); 等同于malloc(10*sizeof(int));
【2】 realloc(p,0); 等同于free
【3】 一般调用方式如下:即使在别处分配新内存,BP->binHeap正确指示
BP->binHeap = (int *)realloc(BP->binHeap, 2*BP->maxSize*sizeof(int));
2017.09.23
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。