堆的实现与堆排序及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问题。