如何实现不修改原数组的Heap Sort：将排序结果存入新数组

• 学习堆排序算法，需要实现一个堆排序函数：接收未排序的原数组作为参数，不修改原数组，将排序后的结果以最小堆顺序存入新数组。
• 了解堆排序的删除逻辑：根节点与最后一个元素交换，堆大小递减，原根节点位置不再属于堆。希望提取原数组中待删除元素存入新数组，全程不改动原数组。
• 当前参考的堆排序C语言代码如下：

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

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // Current Size of the Heap
    int size;
    // Maximum capacity of the heap
    int capacity;
};

int parent(int i) {
    // Get the index of the parent
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    // Return the root node element,
    // since that's the minimum
    return heap->arr[0];
}

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
    minheap->arr = (int*) calloc (capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // Inserts an element to the min heap
    // We first add it to the bottom (last level)
    // of the tree, and keep swapping with it's parent
    // if it is lesser than it. We keep doing that until
    // we reach the root node. So, we will have inserted the
    // element in it's proper position to preserve the min heap property
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    // We can add it. Increase the size and add it to the end
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // Keep swapping until we reach the root
    int curr = heap->size - 1;
    // As long as you aren't in the root node, and while the 
    // parent of the last element is greater than it
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        // Swap
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        // Update the current index of element
        curr = parent(curr);
    }
    return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
    // Rearranges the heap as to maintain
    // the min-heap property
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // Variable to get the smallest element of the subtree
    // of an element an index
    int smallest = index; 
    
    // If the left child is smaller than this element, it is
    // the smallest
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // Similarly for the right, but we are updating the smallest element
    // so that it will definitely give the least element of the subtree
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // Now if the current element is not the smallest,
    // swap with the current element. The min heap property
    // is now satisfied for this subtree. We now need to
    // recursively keep doing this until we reach the root node,
    // the point at which there will be no change!
    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

MinHeap* delete_minimum(MinHeap* heap) {
    // Deletes the minimum element, at the root
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // Update root value with the last element
    heap->arr[0] = last_element;

    // Now remove the last element, by decreasing the size
    heap->size--;
    size--;

    // We need to call heapify(), to maintain the min-heap
    // property
    heap = heapify(heap, 0);
    return heap;
}

MinHeap* delete_element(MinHeap* heap, int index) {
    // Deletes an element, indexed by index
    // Ensure that it's lesser than the current root
    heap->arr[index] = get_min(heap) - 1;
    
    // Now keep swapping, until we update the tree
    int curr = index;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }

    // Now simply delete the minimum element
    heap = delete_minimum(heap);
    return heap;
}

void print_heap(MinHeap* heap) {
    // Simply print the array. This is an
    // inorder traversal of the tree
    printf("Min Heap:\n");
    for (int i=0; i<heap->size; i++) {
        printf("%d -> ", heap->arr[i]);
    }
    printf("\n");
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

int main() {
    // Capacity of 10 elements
    MinHeap* heap = init_minheap(10);

    insert_minheap(heap, 40);
    insert_minheap(heap, 50);
    insert_minheap(heap, 5);
    print_heap(heap);
    
    // Delete the heap->arr[1] (50)
    delete_element(heap, 1);

    print_heap(heap);
    free_minheap(heap);
    return 0;
}

该需求完全可行，核心思路是先基于原数组复制构建临时最小堆，再依次提取堆顶最小值存入结果数组，同时维护堆结构，全程不触碰原数组。以下是修改后的完整代码，新增了heap_sort函数实现需求：

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

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    int size;
    int capacity;
};

int parent(int i) {
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    return heap->arr[0];
}

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc(1, sizeof(MinHeap));
    minheap->arr = (int*) calloc(capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

MinHeap* insert_minheap(MinHeap* heap, int element) {
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    heap->size++;
    heap->arr[heap->size - 1] = element;

    int curr = heap->size - 1;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }
    return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 
    int smallest = index; 
    
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

MinHeap* delete_minimum(MinHeap* heap) {
    if (!heap || heap->size == 0)
        return heap;

    int last_element = heap->arr[heap->size-1];
    heap->arr[0] = last_element;
    heap->size--;

    heap = heapify(heap, 0);
    return heap;
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

// 新增的堆排序函数：不修改原数组，返回排序后的最小堆数组
int* heap_sort(const int* original_arr, int size, int* result_size) {
    // 构建临时最小堆，复制原数组所有元素
    MinHeap* heap = init_minheap(size);
    for (int i = 0; i < size; i++) {
        insert_minheap(heap, original_arr[i]);
    }

    // 分配结果数组内存
    int* sorted_arr = (int*)malloc(size * sizeof(int));
    *result_size = size;

    // 依次提取堆顶最小值存入结果数组，每次提取后维护堆结构
    for (int i = 0; i < size; i++) {
        sorted_arr[i] = get_min(heap);
        delete_minimum(heap);
    }

    // 释放临时堆内存
    free_minheap(heap);
    return sorted_arr;
}

int main() {
    int original_arr[] = {40, 50, 5, 10, 30, 20};
    int size = sizeof(original_arr) / sizeof(original_arr[0]);
    int result_size;

    printf("原数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", original_arr[i]);
    }
    printf("\n");

    // 调用堆排序函数
    int* sorted_arr = heap_sort(original_arr, size, &result_size);

    printf("排序后的最小堆数组：");
    for (int i = 0; i < result_size; i++) {
        printf("%d ", sorted_arr[i]);
    }
    printf("\n");

    // 验证原数组未被修改
    printf("原数组未修改：");
    for (int i = 0; i < size; i++) {
        printf("%d ", original_arr[i]);
    }
    printf("\n");

    // 释放结果数组内存
    free(sorted_arr);
    return 0;
}

代码说明 #

1. heap_sort函数：接收原数组（用const确保不被修改）、数组大小，返回排序后的新数组，同时通过result_size返回结果数组的大小。
2. 临时堆构建：复制原数组元素到临时最小堆中，完全不修改原数组。
3. 结果生成：每次提取堆顶最小值存入结果数组，然后删除堆顶并调用heapify维护堆结构，最终结果数组既是升序排列，也符合最小堆的结构特性（升序数组本身就是一个合法的最小堆）。

内容的提问来源于stack exchange，提问作者User617290653251457439