编辑代码

#include <iostream>
#include <cmath>
using namespace std;

class HeapFromBottom {
private:
    int *heap;
    int capacity;

    void heapify(int nodeIndex, int heapBottom) {
        // 计算最后一个父节点的索引
        int lastParentIndex = floor(heapBottom / 2);

        while (nodeIndex <= lastParentIndex) {
            // 计算左子节点的索引
            int leftChildIndex = 2 * nodeIndex;
            int maxIndex = leftChildIndex;

            // 比较左右子节点，找出值较大的索引
            if ((leftChildIndex + 1 <= heapBottom) && (heap[leftChildIndex + 1] > heap[leftChildIndex])) {
                maxIndex = leftChildIndex + 1;
            }

            // 如果父节点的值小于最大子节点的值，则交换它们
            if (heap[nodeIndex] < heap[maxIndex]) {
                int temp = heap[nodeIndex];
                heap[nodeIndex] = heap[maxIndex];
                heap[maxIndex] = temp;

                // 更新节点索引，继续向下调整
                nodeIndex = maxIndex;
            } else {
                // 如果父节点的值大于等于最大子节点的值，则堆调整完成
                break;
            }
        }
    }

public:
    HeapFromBottom(int arr[], int length) {
        // 动态分配堆数组的内存
        heap = new int[length + 1];
        capacity = length;

        // 将输入数组复制到堆数组中
        for (int i = 0; i < length; ++i) {
            heap[i + 1] = arr[i];
        }

        // 计算最后一个父节点的索引，然后进行堆调整
        int lastParentIndex = floor(length / 2);
        for (int i = lastParentIndex; i >= 1; --i) {
            heapify(i, capacity);
        }
    }

    // 析构函数，释放堆数组的内存
    ~HeapFromBottom() {
        delete[] heap;
    }

    // 堆排序函数
    void sort() {
        int heapTop = 1;
        int heapBottom = capacity;

        // 只剩堆顶元素时排序完成
        while (heapTop < heapBottom) {
            // 将堆顶元素与堆的最后一个元素交换位置
            int temp = heap[heapTop];
            heap[heapTop] = heap[heapBottom];
            heap[heapBottom] = temp;

            // 缩小堆的大小，进行堆调整
            --heapBottom;
            heapify(heapTop, heapBottom);
        }
    }

    // 打印堆数组元素
    void print() {
        for (int i = 1; i < capacity + 1; ++i) {
            cout << heap[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    // 输入数组
    int arr[] = {2, 9, 7, 6, 5, 8};

    // 创建堆对象，并打印初始堆数组
    HeapFromBottom *heap = new HeapFromBottom(arr, sizeof(arr) / sizeof(int));
    cout << "初始堆数组: ";
    heap->print();

    // 进行堆排序，并打印排序后的数组
    heap->sort();
    cout << "堆排序后的数组: ";
    heap->print();

    // 释放堆对象的内存
    delete heap;

    return 0;
}