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

堆的实现与堆排序及TopK问题的C语言代码

下面是详细的堆实现，包括向上调整、向下调整算法，以及堆排序和解决TopK问题的完整C语言示例代码。

1. 堆的实现

首先，定义堆的数据结构：

#include <stdio.h>
#include <stdlib.h>

#define MAX_HEAP_SIZE 100

typedef 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问题。