编辑代码

#include <stdio.h>  
#include <stdlib.h>  
#include <math.h>  
  
#define PRIVATE 0  
#define PUBLIC 1  
  
typedef struct {  
    int *heap;  
    int capacity;  
} HeapFromBottom;  
  
void heapify(int nodeIndex, int heapBottom, HeapFromBottom *heap) {  
    int lastParentIndex = heapBottom / 2;  
    while (nodeIndex <= lastParentIndex) {  
        int leftChildIndex = 2 * nodeIndex;  
        int maxIndex = leftChildIndex;  
        if (leftChildIndex + 1 <= heapBottom && heap->heap[leftChildIndex + 1] > heap->heap[leftChildIndex]) {  
            maxIndex = leftChildIndex + 1;  
        }  
        if (heap->heap[nodeIndex] < heap->heap[maxIndex]) {  
            int temp = heap->heap[nodeIndex];  
            heap->heap[nodeIndex] = heap->heap[maxIndex];  
            heap->heap[maxIndex] = temp;  
            nodeIndex = maxIndex;  
        } else {  
            break;  
        }  
    }  
}  
  
HeapFromBottom* HeapFromBottom_new(int arr[], int length) {  
    HeapFromBottom *heap = (HeapFromBottom*)malloc(sizeof(HeapFromBottom));  
    heap->heap = (int*)malloc((length + 1) * sizeof(int));  
    heap->capacity = length;  
    for (int i = 0; i < length; ++i) {  
        heap->heap[i + 1] = arr[i];  
    }  
    int lastParentIndex = heap->capacity / 2;  
    for (int i = lastParentIndex; i > 0; --i) {  
        heapify(i, heap->capacity, heap);  
    }  
    return heap;  
}  
  
void HeapFromBottom_sort(HeapFromBottom *heap) {  
    int heapTop = 1;  
    int heapBottom = heap->capacity;  
    while (heapTop < heapBottom) {  
        int temp = heap->heap[heapTop];  
        heap->heap[heapTop] = heap->heap[heapBottom];  
        heap->heap[heapBottom] = temp;  
        --heapBottom;  
        heapify(heapTop, heapBottom, heap);  
    }  
}  
  
void HeapFromBottom_print(HeapFromBottom *heap) {  
    for (int i = 1; i < heap->capacity + 1; ++i) {  
        printf("%d ", heap->heap[i]);  
    }  
    printf("\n");  
}  
  
int main() {  
    int arr[] = {2, 9, 7, 6, 5, 8};  
    HeapFromBottom *heap = HeapFromBottom_new(arr, sizeof(arr) / sizeof(int));  
    HeapFromBottom_print(heap);  
    HeapFromBottom_sort(heap);  
    HeapFromBottom_print(heap);  
    free(heap->heap);  
    free(heap);  
    return 0;  
}