堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言

堆的实现与堆排序及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;
}

解释

1. 堆的实现：使用数组和一个结构体来表示堆，包含堆的数据和大小。
2. 向上调整算法：在插入新元素后，通过比较当前节点和父节点的值来调整堆，确保堆的性质。
3. 向下调整算法：在删除堆顶元素后，通过比较当前节点和子节点的值来调整堆，确保堆的性质。
4. 堆排序：利用堆的插入和删除操作，将数组中的元素排序。
5. TopK问题：使用最小堆找出数据流中前K大的元素。

通过这些步骤和代码实现，可以高效地进行堆操作、堆排序以及解决TopK问题。