DS内排—堆排序

题目描述

给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。

输入

数据个数n，n个整数数据

输出

初始创建的小顶堆序列

每趟交换、筛选后的数据序列，输出格式见样例

输入样例1

8 34 23 677 2 1 453 3 7

输出样例1

8 1 2 3 7 23 453 677 34
8 2 7 3 34 23 453 677 1
8 3 7 453 34 23 677 2 1
8 7 23 453 34 677 3 2 1
8 23 34 453 677 7 3 2 1
8 34 677 453 23 7 3 2 1
8 453 677 34 23 7 3 2 1
8 677 453 34 23 7 3 2 1

AC代码

#include <bits/stdc++.h>
using namespace std;


class MinHeap {
private:
    vector<int> heap; //用于存储堆的数组

    //下滤操作，用于维护堆的性质
    void heapifyDown(int index, int size) {
        while (true) {
            int left = 2 * index + 1; // 左子节点的索引
            int right = 2 * index + 2; // 右子节点的索引
            int smallest = index; // 当前最小值的索引

            // 如果左子节点存在且小于当前最小值，更新最小值索引
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            // 如果右子节点存在且小于当前最小值，更新最小值索引
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
            // 如果最小值索引发生变化，交换当前节点和最小值节点，并继续下滤
            if (smallest != index) {
                swap(heap[index], heap[smallest]);
                index = smallest;
            } else {
                break; // 如果没有变化，结束下滤
            }
        }
    }

public:
    void buildHeap(vector<int>& arr) {
        heap = arr; // 将输入数组赋值给堆
        int n = heap.size(); // 堆的大小
        // 从最后一个非叶子节点开始，向上进行下滤操作
        for (int i = n / 2 - 1; i >= 0; --i) {
            heapifyDown(i, n);
        }
    }

    // 堆排序
    void heapSort() {
        int n = heap.size(); // 堆的大小
        // 从最后一个元素开始，将堆顶元素与最后一个元素交换，然后重新调整堆
        for (int i = n - 1; i > 0; --i) {
            swap(heap[0], heap[i]); // 交换堆顶元素和最后一个元素
            heapifyDown(0, i); // 重新调整堆
            printHeap(); // 输出当前堆的状态
        }
    }

    void printHeap() {
        cout << heap.size() << " "; // 输出堆的大小
        for (int i = 0; i < heap.size() - 1; ++i) {
            cout << heap[i] << " "; // 输出堆的元素，除了最后一个元素
        }
        cout << heap[heap.size() - 1] << endl; // 输出最后一个元素
    }
};

int main() {
    int n;
    cin >> n; 
    vector<int> arr(n); 
    for (int i = 0; i < n; ++i) {
        cin >> arr[i]; 
    }

    MinHeap heap; // 创建最小堆对象
    heap.buildHeap(arr); // 构建最小堆
    heap.printHeap(); // 输出初始创建的小顶堆序列
    heap.heapSort(); // 进行堆排序，并输出每趟交换、筛选后的数据序列

    return 0;
}