建设e购物网站,wordpress图片模板下载,邯郸网站设计价位,建筑人才网证书查询堆数据结构是一种数组对象#xff0c;它可以被看作一颗完全二叉树的结构#xff08;数组是完全二叉树#xff09;#xff0c;堆是一种静态结构。堆分为最大堆和最小堆。最大堆#xff1a;每个父结点都大于孩子结点。最小堆#xff1a;每个父结点都小于孩子结点。堆的优势…堆数据结构是一种数组对象它可以被看作一颗完全二叉树的结构数组是完全二叉树堆是一种静态结构。堆分为最大堆和最小堆。最大堆每个父结点都大于孩子结点。最小堆每个父结点都小于孩子结点。堆的优势效率高可以找最大数最小数增删的时间复杂度为lgN怎么找最后一个叶子结点找到最后一个叶子结点左孩子为空就是叶子结点由于堆是静态结构所以我们要通过计算下标的方法找计算它的孩子是否超出了数组范围。通过观察可以总结数组下标计算父子关系的公式leftchild parent*2 1 rightchild parent*2 1parent ( child -1) /21.代码实现typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;
Heap结构体中有一个指向动态数组的指针size表示数组的当前元素个数capacity表示数组的容量将结构体的定义和函数的申明都放在Heap.h中#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;//以数组的形式打印堆的元素
void PrintHeap(HP* php);
//初始化堆
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);//插入数据x 但是要依旧保持堆的形态
void HeapPush(HP* php, HPDataType x);//删除堆顶的元素
void HeapPop(HP* php);//返回堆顶的元素
HPDataType HeapTop(HP* php);
//判定堆是否为空
bool HeapEmpty(HP* php);
//返回堆当前元素的个数
int HeapSize(HP* php);在Heap.c文件中完成接口的实现初始化void HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;}插入元素void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}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 (child - 1) / 2; }else {break;}}
}
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity) //检查容量{int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail!);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}HeapPush函数插入元素将对象的指针传过来并且将要插入的元素传过来插入元素前检查容量当size capacity时就得扩容我们采用的是将原来的容量扩大两倍因为两倍比较合适。定义一个新的容量当之前的容量为0时给4个字节的大小之前有容量时扩大到原来的两倍。这里需要注意的时realloc是在原来的基础上扩大的字节数所以要记得newcapacity*sizeof(HPDataType)!再将a指向扩容后的地址然后更新capacity的大小在size位置插入元素x然后size。在这里模拟实现的是小堆但是插入数据的位置在逻辑结构的数组的尾部或者说是在完全二叉树的叶子节点位置。小堆结构的最小的元素都在较上方所以说要向上调整。将数组的指针和插入元素的数组下标传给向上调整函数。AdjustUp函数通过公式计算出插入元素的数组下标的父节点的数组下标。假设插入的位置在最下方的红色部分小堆就是父节点要比子节点的值小如果插入的元素的值很小需要一直和当前位置的父节点交换位置那交换最多的情况就是从叶子节点的位置交换到根节点的位置(也就是说child0时因为交换的次数不确定所以放到for不好控制所以将向上调整的动作放到while循环里当符合条件时跳出循环即可。当child0时,a[child] a[parent]所以进行交换将parent的下标的值给child然后再次计算出该节点位置的父节点的数组下标再次比较该节点与其父节点的值的大小如果符合调整的条件就进行交换一直循环。当child0或者a[parent]a[parent]的值就不需要就跳出循环向上调整结束新插入的元素就到了应该到的位置。 Swap函数取出要交换的值的地址交给该函数创建一个同类型的变量tmp存储p1指向的内容p1再指向p2所指向的内容最后再将p2指向tmp就完成了值的交换。通过这三个函数就完成了数据的插入同时保持了堆的形态。删除堆顶的元素首先明白小堆和大堆的应用时为了找到前n个最小或者最大的元素删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。void AdjustDown(HPDataType* a, int n, int parent)
{int minChild parent * 2 1; //默认最小的孩子是左孩子while (minChild n){if (minChild 1 n a[minChild 1] a[minChild]){minChild; }if (a[minChild] a[parent]) {Swap(a[minChild], a[parent]); parent minChild; minChild parent * 2 1; }else {break;}}}
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]); //将根部元素与最后一个元素交换然后再向下调整php-size--; //相当于删除了最后一个元素AdjustDown(php-a, php-size, 0);
}
删除堆顶元素首先保证堆有元素再交换堆顶元素和最后一个元素size--就相当于删除了最后一个元素再调用向下调整函数。将数组的地址和数组的元素个数还有数组的首元素下标传给向下调整函数开始调整。模拟实现的是小堆所以较大的元素在堆的下方小的元素在较上方每一个父节点都有两个子节点所以该和谁交换使得根节点的数据往下调整呢 首先根据父节点的数组下标得出左孩子的数组下标默认最小孩子minChild为左孩子如果右孩子比左孩子小那就让minChild1将这个调整最小孩子的动做放到while循环中因为每一次调整都得和最小孩子交换位置。循环调整的停止条件是minChild小于n因为要保证交换的元素下标是在数组范围内的不能越界交换这个条件也是循环最多次的条件。当a[minChild] a[parent]时就进行交换调整。当父亲和最小孩子的值相等或者小于最小孩子的值 那就跳出循环 向下调整完成。打印堆元素以数组的形式打印void PrintHeap(HP* php)
{for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}判空bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
取堆顶元素//返回堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}
元素个数int HeapSize(HP* php)
{assert(php);return php-size;
}销毁void HeapDestory(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
2.测试用例#includeHeap.hint main()
{HP hp;HeapInit(hp);int arr[] { 65,100,70,32,50,60 };for (int i 0; i sizeof(arr) / sizeof(int); i){HeapPush(hp, arr[i]);}while (!HeapEmpty(hp)) //不为空时{printf(%d , HeapTop(hp)); //打印堆顶的元素HeapPop(hp); //删除堆顶的元素 三行代码就实现了出堆调整打印堆顶元素} //一直循环直到堆为空时循环停止HeapDestory(hp); //销毁堆return 0;
}3.整体代码test.c:#includeHeap.hint main()
{HP hp;HeapInit(hp);int arr[] { 65,100,70,32,50,60 };for (int i 0; i sizeof(arr) / sizeof(int); i){HeapPush(hp, arr[i]);}while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}HeapDestory(hp);return 0;
}Heap.c:#includeHeap.hvoid HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;}
void HeapDestory(HP* php)
{free(php-a);php-a NULL;}void PrintHeap(HP* php)
{for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}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 (child - 1) / 2; //相当于现在是孙子和爷爷位置的比较}else //当孩子大于等于父亲的值时就不用调整了可以退出循环{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)//向下调整 数组传过来 数组的大小 根节点的下标
{int minChild parent * 2 1; //默认最小的孩子是左孩子while (minChild n){if (minChild 1 n a[minChild 1] a[minChild]){minChild; //当右孩子比左孩子小 那么最小的孩子就变为右孩子}if (a[minChild] a[parent]) //当父亲比孩子大时 那父亲就要和孩子交换位置{Swap(a[minChild], a[parent]); //调用交换函数 交换值parent minChild; //交换完成后父亲还要继续和下边的孩子比较 将最小孩子的位置给给父亲minChild parent * 2 1; //父亲来到了上一个最小孩子的位置此时这个位置的下一行的最小孩子又默认为左孩子继续比较 }else //当父亲和最小孩子的值相等或者小于最小孩子的值 那就跳出循环 向下调整完成{break;}}}//插入x 保持堆形态
void HeapPush(HP* php, HPDataType x) //用结构体的指针接收对象的指针 接收 最后一个元素
{assert(php);if (php-size php-capacity) //检查容量{int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail!);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1); //传过去对象的指针 和对象的最后一个元素
}//删除堆顶的元素----为了找到次大的元素
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]); //将根部元素与最后一个元素交换然后再向下调整php-size--; //相当于删除了最后一个元素AdjustDown(php-a, php-size, 0);
}//返回堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php-size 0;}int HeapSize(HP* php)
{assert(php);return php-size;
}Heap.h#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;void PrintHeap(HP* php);void HeapInit(HP* php);
void HeapDestory(HP* php);//插入数据x 继续保持堆的形态
void HeapPush(HP* php, HPDataType x);//删除堆顶的元素
void HeapPop(HP* php);//返回堆顶的元素
HPDataType HeapTop(HP* php);bool HeapEmpty(HP* php);int HeapSize(HP* php);
