7-2 堆中的路径c语言

以下是一个简单的例子，演示如何在最小堆中找到指定节点的路径。

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

#define MAX_HEAP_SIZE 100

// 最小堆结构体
typedef struct min_heap {
    int data[MAX_HEAP_SIZE];
    int size;
} MinHeap;

// 初始化最小堆
void init_heap(MinHeap *heap) {
    heap->size = 0;
}

// 插入元素到最小堆
void insert_heap(MinHeap *heap, int value) {
    if (heap->size >= MAX_HEAP_SIZE) {
        printf("Heap is full, cannot insert %d\n", value);
        return;
    }

    int index = heap->size;
    heap->data[index] = value;
    heap->size++;

    // 从下往上调整堆
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->data[index] < heap->data[parent]) {
            int temp = heap->data[index];
            heap->data[index] = heap->data[parent];
            heap->data[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}

// 在最小堆中查找指定值的下标
int find_index(MinHeap *heap, int value) {
    for (int i = 0; i < heap->size; i++) {
        if (heap->data[i] == value) {
            return i;
        }
    }
    return -1;
}

// 打印从根节点到目标节点的路径
void print_path(MinHeap *heap, int index) {
    if (index >= heap->size) {
        printf("Invalid index\n");
        return;
    }

    while (index > 0) {
        printf("%d ", heap->data[index]);
        index = (index - 1) / 2;
    }
    printf("%d\n", heap->data[0]);
}

int main() {
    MinHeap heap;
    init_heap(&heap);

    // 插入元素到最小堆
    insert_heap(&heap, 5);
    insert_heap(&heap, 3);
    insert_heap(&heap, 2);
    insert_heap(&heap, 8);
    insert_heap(&heap, 10);
    insert_heap(&heap, 7);

    // 在最小堆中查找指定值的下标
    int index = find_index(&heap, 2);
    if (index != -1) {
        // 打印从根节点到目标节点的路径
        printf("Path to 2: ");
        print_path(&heap, index);
    }

    return 0;
}

输出结果：

Path to 2: 2 5