福州网站建设模板,厦门电商网站建设,十大免费软件不收费安卓,网站开发流程百度文库目录 堆的概念及结构 编辑 堆的实现 实现堆的接口#xff1a; 堆的初始化#xff1a; 堆的打印#xff1a; 堆的销毁#xff1a; 获取最顶的根数据#xff1a; 交换#xff1a; 堆的插入#xff1a;#xff08;插入最后#xff09; 向上调整#xff1a;#xff0… 目录 堆的概念及结构 编辑 堆的实现 实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据 交换 堆的插入插入最后 向上调整这次用的是小堆 堆的删除删除根 向下调整这次用的小堆 堆排序 堆的概念及结构 如果有一个关键码的集合 K { … }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 ( 且 ) i 0 1 2…则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 小根堆父亲节点大于等于孩子节点 大根堆父亲节点小于等于孩子节点 堆的实现
实现堆的接口
#define CRT_SECURE_NO_WARNING 1
#pragma once
#includestdio.h
#includestdlib.h
#includestring.h
#includeassert.h
#includestdbool.h//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void AdjustUp(HPDataType* a, int child);void AdjustDown(HPDataType* a, int n, int parent);//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);
堆的初始化
//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}
堆的打印
void HeapPrint(HP* php)
{assert(php);//最后一个孩子下标为size-1for (size_t i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}堆的销毁
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
获取最顶的根数据
//获取根数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
堆的插入插入最后
先考虑扩容将数据插到最后再用向上调整法。
//插入数据
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity)//有效元素个数和容量是否相等{//相等的情况分两种1.容量为0先扩4个sizeof 2.容量占用满了,扩2个int newCapacity php-capacity 0 ? 4 : php-capacity * 2;//返回扩容后的内存新地址 //扩容后的新大小HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}//扩容后的新地址php-a tmp;//新容量php-capacity newCapacity;}// php-size下标位置 先将x放最后后面再调整php-a[php-size] x;// 有效数据php-size;// 向上调整 //size-1为新插入数据的下标AdjustUp(php-a, php-size - 1);}
向上调整这次用的是小堆
//向上调整 //新插入的数据下标
void AdjustUp(HPDataType* a, int child)
{ //定义其父节点的下标int parent (child - 1) / 2;//循环while (child 0){//如果子小于父就交换 小堆if (a[child] a[parent]){//数值交换Swap(a[child], a[parent]);//下标child parent;parent (parent - 1) / 2;}else{break;}}
}
堆的删除删除根
先判空看下是否还有元素可以删除。根数据先和最后一个孩子交换位置孩子再向下调整。
//删除
void HeapPop(HP* php)
{assert(php);//确保有元素可删assert(php-size 0);//最后一个孩子和要删除的根交换Swap(php-a[0], php-a[php-size - 1]);//有效元素size减减相当于删除了交换后的原来的根--php-size;//删除后向下调整AdjustDown(php-a, php-size, 0);}
向下调整这次用的小堆
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;//n下标位置已经没有数了while (child n){//选小的孩子往上浮小堆if (child 1 n a[child 1] a[child]){child;}//若小的孩子都小于父则交换if (a[child] a[parent]){Swap(a[child], a[parent]);//交换后下来的数重新变成parent继续向下调整parent child;child parent * 2 1;}}
}
堆排序 1. 建堆 升序建大堆 降序建小堆 2. 利用堆删除思想来进行排序 如建的大堆排升序可以用堆删除思想向下调整法将栈顶和最后一个元素交换依次将最大的次大的......往后放就达到了升序排列。 void HeapSort(int* a, int n)
{//建堆 这里可以选建大堆还是小堆for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
