南山区住房与建设局官方网站,西双版纳 网站建设,深圳大森设计,app开发费用计入什么科目大根堆小根堆的实现#xff1a;以PPT形式呈现大根堆构建的理论过程1、首先涉及到一个堆的调整#xff0c;这也是算法的核心部分。假设树中#xff0c;节点i的子树已经为两个大根堆。这两个子树再加上i节点的话#xff0c;可能是大根堆也可能不是#xff0c;因此需要对节点…大根堆小根堆的实现以PPT形式呈现大根堆构建的理论过程1、首先涉及到一个堆的调整这也是算法的核心部分。假设树中节点i的子树已经为两个大根堆。这两个子树再加上i节点的话可能是大根堆也可能不是因此需要对节点i进行调整。若i小于left(i) or right(i)需要将i下移。2、这是一个例子需要将4下移。满足大根堆的性质。3、大根堆的调整算法。假设i节点的两个子树已经是大根堆。对应代码中MaxHeapify()函数。4、算法正确性分析。5、构建大根堆的过程中只需要考虑n/2 1 之前的节点因为之后的节点都是叶节点。6、构建大根堆的算法。对应代码中MaxHeapCreat()函数#include #include #include #include #include /*目的建立大根堆也可以变成小根堆核心堆的调整输入一系列来自文件的整数。文件中整数以空格隔开输出大根堆*/void Swap(uint32_t* array, uint32_t i, uint32_t j){assert(array);uint32_t tmp;tmp array[j];array[j] array[i];array[i] tmp;}/*大根堆调整*/void MaxHeapify(uint32_t* array, uint32_t heapSize, uint32_t currentNode){uint32_t leftChild, rightChild, largest;leftChild 2*currentNode 1;rightChild 2*currentNode 2;if(leftChild heapSize array[leftChild] array[currentNode])largest leftChild;elselargest currentNode;if(rightChild heapSize array[rightChild] array[largest])largest rightChild;if(largest ! currentNode){Swap(array, largest, currentNode);MaxHeapify(array, heapSize, largest);}}/*构建大根堆*/void MaxHeapCreat(uint32_t* array, uint32_t heapSize){int i;for(i heapSize/2; i 0; i--){MaxHeapify(array, heapSize, i);}}/*小根堆调整*/void MinHeapify(uint32_t* array, uint32_t heapSize, uint32_t currentNode){uint32_t leftChild, rightChild, minimum;leftChild 2*currentNode 1;rightChild 2*currentNode 2;if(leftChild heapSize array[leftChild] array[currentNode])minimum leftChild;elseminimum currentNode;if(rightChild heapSize array[rightChild] array[minimum])minimum rightChild;if(minimum ! currentNode){Swap(array, minimum, currentNode);MinHeapify(array, heapSize, minimum);}}/*构建小根堆*/void MinHeapCreat(uint32_t* array, uint32_t heapSize){int i;for(i heapSize/2; i 0; i--){MinHeapify(array, heapSize, i);}}int main(){uint32_t tmp;uint32_t *array;array malloc(sizeof(uint32_t));int i, heapSize 0;/*从文件中读出待排序数据*/char* filePathway C:/Users/Administrator/Desktop/data.txt;FILE* fp;fp fopen(filePathway, rb);if(!fp){fprintf(stderr, Can not open file correctly\n);}while(!feof(fp)){fscanf(fp, %d, tmp);heapSize;array realloc(array, sizeof(uint32_t) * (heapSize ));if(array NULL){fprintf(stderr, realloc error!\n);return 1;}array[heapSize - 1] tmp;}printf(The origen dataset:\n);for(i 0; i heapSize; i){printf(%d\t, array[i]);}printf(\n);/*构建小根堆并输出*/MinHeapCreat(array, heapSize);printf(Output the MinHeap:\n);for(i 0; i heapSize; i){printf(%d\t, array[i]);}printf(\n);/*构建大根堆并输出*/MaxHeapCreat(array, heapSize);printf(Output the MaxHeap:\n);for(i 0; i heapSize; i){printf(%d\t, array[i]);}free(array);fclose(fp);return 0;}
