宝塔服务器搭建网站教程,生态旅游网站的建设的内容,网站源码修复,企业如何应用网站的堆的实现与堆排序及TopK问题的C语言代码
下面是详细的堆实现#xff0c;包括向上调整、向下调整算法#xff0c;以及堆排序和解决TopK问题的完整C语言示例代码。
1. 堆的实现
首先#xff0c;定义堆的数据结构#xff1a;
#include stdio.h
#include stdli…堆的实现与堆排序及TopK问题的C语言代码
下面是详细的堆实现包括向上调整、向下调整算法以及堆排序和解决TopK问题的完整C语言示例代码。
1. 堆的实现
首先定义堆的数据结构
#include stdio.h
#include stdlib.h#define MAX_HEAP_SIZE 100typedef struct {int data[MAX_HEAP_SIZE];int size;
} Heap;Heap* createHeap() {Heap* heap (Heap*)malloc(sizeof(Heap));heap-size 0;return heap;
}2. 向上调整算法
void heapifyUp(Heap* heap, int index) {int parentIndex (index - 1) / 2;if (index 0 heap-data[index] heap-data[parentIndex]) {// 交换当前节点和父节点int temp heap-data[index];heap-data[index] heap-data[parentIndex];heap-data[parentIndex] temp;// 递归向上调整heapifyUp(heap, parentIndex);}
}3. 向下调整算法
void heapifyDown(Heap* heap, int index) {int largest index;int leftChild 2 * index 1;int rightChild 2 * index 2;if (leftChild heap-size heap-data[leftChild] heap-data[largest]) {largest leftChild;}if (rightChild heap-size heap-data[rightChild] heap-data[largest]) {largest rightChild;}if (largest ! index) {// 交换当前节点和最大子节点int temp heap-data[index];heap-data[index] heap-data[largest];heap-data[largest] temp;// 递归向下调整heapifyDown(heap, largest);}
}4. 插入元素到堆
void insertHeap(Heap* heap, int value) {if (heap-size MAX_HEAP_SIZE) {printf(Heap is full!\n);return;}heap-data[heap-size] value;heap-size;heapifyUp(heap, heap-size - 1);
}5. 删除堆顶元素
int extractMax(Heap* heap) {if (heap-size 0) {printf(Heap is empty!\n);return -1;}int maxValue heap-data[0];heap-data[0] heap-data[heap-size - 1];heap-size--;heapifyDown(heap, 0);return maxValue;
}6. 堆排序
void heapSort(int* array, int length) {Heap* heap createHeap();for (int i 0; i length; i) {insertHeap(heap, array[i]);}for (int i length - 1; i 0; i--) {array[i] extractMax(heap);}free(heap);
}7. TopK问题
解决TopK问题即找出数据流中前K大的元素可以使用一个最小堆来实现。
void topK(int* array, int length, int k) {if (k 0 || k length) {printf(Invalid value of K!\n);return;}Heap* heap createHeap();for (int i 0; i k; i) {insertHeap(heap, array[i]);}for (int i k; i length; i) {if (array[i] heap-data[0]) {heap-data[0] array[i];heapifyDown(heap, 0);}}printf(Top %d elements: , k);for (int i 0; i k; i) {printf(%d , extractMax(heap));}printf(\n);free(heap);
}8. 测试代码
int main() {int array[] {3, 2, 1, 5, 6, 4};int length sizeof(array) / sizeof(array[0]);// 测试堆排序heapSort(array, length);printf(Sorted array: );for (int i 0; i length; i) {printf(%d , array[i]);}printf(\n);// 测试TopK问题int k 3;int array2[] {3, 2, 1, 5, 6, 4};length sizeof(array2) / sizeof(array2[0]);topK(array2, length, k);return 0;
}解释
堆的实现使用数组和一个结构体来表示堆包含堆的数据和大小。向上调整算法在插入新元素后通过比较当前节点和父节点的值来调整堆确保堆的性质。向下调整算法在删除堆顶元素后通过比较当前节点和子节点的值来调整堆确保堆的性质。堆排序利用堆的插入和删除操作将数组中的元素排序。TopK问题使用最小堆找出数据流中前K大的元素。
通过这些步骤和代码实现可以高效地进行堆操作、堆排序以及解决TopK问题。
