#include <bits/stdc++.h>
using namespace std;
const int MaxData = 1024;
using ElementType  = int;
struct HNode {
    ElementType *Data;
    int Size;
    int Capacity;
};

using MinHeap = struct HNode *;
MinHeap MinCreate(int MaxSize);
MinHeap  CreateMinHeap(int arr [], int len);
void MinHeap_Insert(MinHeap H, ElementType item);
ElementType DeleteMin(MinHeap H);
void MinHeap_Adjust(MinHeap H);
MinHeap HeapSort(MinHeap H);
MinHeap HeapSort(MinHeap H, int n);
bool IsFull(MinHeap H);
bool IsEmpty(MinHeap H);
int getSize(MinHeap H);

void Test()
{
    int len = 12;
    int arr [] = {142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102};
    MinHeap H = CreateMinHeap(arr, len);
    H = HeapSort(H);
    // H = HeapSort(H, H->Size);
    for (int i = 1; i <= H->Capacity; ++i) {
        cout << H->Data[i] << " ";
    }
    cout << endl;
}

int main()
{

    //Test2();
    Test();
    return 0;
}
MinHeap MinCreate(int MaxSize)
{
    MinHeap H = new (struct HNode);
    H->Data = new ElementType[MaxSize+1];  // 下标从1开始
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MaxData;  // 哨兵，比所有优先级都大
    return H;
}

MinHeap CreateMinHeap(int arr[], int len)
{
    MinHeap H = MinCreate(len);
    for (int i = 0; i <= len - 1; ++i) {
        H->Data[++H->Size] = arr[i];
    }
    MinHeap_Adjust(H);
    return H;
}

void MinHeap_Insert(MinHeap H, ElementType item)
{
    int i;
    if (IsFull(H)) {
        cout << "堆已满" << endl;
        return;
    }
    i = ++H->Size;
    for ( ; i >= 2 && H->Data[i/2] > item; i /= 2) {
        H->Data[i] = H->Data[i/2];
    }
    H->Data[i] = item;
}

ElementType DeleteMin(MinHeap H)
{ // 从堆中取出键值最大的元素，并删除一个节点       // O(logN)
    int parent, child;
    ElementType MinItem, temp;
    if (IsEmpty(H)) {
        cout << "最小堆为空" << endl;
        return - 1;
    }
    MinItem = H->Data[1]; // 取出根节点最大值
    temp = H->Data[H->Size--]; // 用最大堆中最后一个元素从更节点开始向上过滤下层节点
    for (parent = 1; parent * 2 <= H->Size; parent = child) {
        child = parent * 2;
        if ((child != H->Size) && (H->Data[child] > H->Data[child+1])) {
            child += 1;  // child指向左右节点较大者
        }
        if (temp <= H->Data[child]) {
            //H->Data[parent] = temp;  // 加在这里是错误的
            break;
        } else {  // 移动temp到下一层
            H->Data[parent] = H->Data[child];
        }
    }
    H->Data[parent] = temp; //这个必须有

   /* for (int i = 1; i <= H->Size; ++i) {
        cout << H->Data[i] << " ";
    }
    cout << endl;*/
    return MinItem;
}

void MinHeap_Adjust(MinHeap H)
{
    for (int parent = H->Size / 2; parent >= 1; --parent) {
        ElementType temp = H->Data[parent];
        int child = 2 * parent;
        while (child <= H->Size) {
            if ((child + 1) <= H->Size && H->Data[child + 1] <= H->Data[child]) {
                child += 1;
            }
            if (temp <= H->Data[child]) {
                H->Data[child / 2] = temp;
                break;
            }
            H->Data[child / 2] = H->Data[child];
            H->Data[child] = temp;
            child = 2 * child;
        }
    }
}

MinHeap HeapSort(MinHeap H)
{
    for (int i = 1; i <= H->Capacity; ++i) {
        // H->Data[H->Size + 1] = DeleteMin(H);  错误
        // H->Data[H->Size] = DeleteMin(H); 正确
        int item = DeleteMin(H);
        H->Data[H->Size + 1] = item;
    }
    return H;
}

MinHeap HeapSort(MinHeap H, int n)
{
    if (n == 0) {
        return H;
    } else {
        // H->Data[H->Size + 1] = DeleteMin(H);  错误
        // H->Data[H->Size] = DeleteMin(H); 正确
        int item = DeleteMin(H);
        H->Data[H->Size + 1] = item;
        return HeapSort(H, H->Size - 1);
    }
}

bool IsFull(MinHeap H)
{
    return H->Size == H->Capacity;
}

bool IsEmpty(MinHeap H)
{
    return H->Size == 0;
}

int getSize(MinHeap H)
{
    return H->Size;
}

emmm！写作业的时候，刚好将之前的堆操作简单的复习了一下，不过单纯手码的话会调很久吧！！

❌不过这里有点疑惑🙏

在HeapSort函数里，为什么我注释掉的那部分

// H->Data[H->Size + 1] = DeleteMin(H);

结果就是错的，而先DeleteMin，然后赋值就是正确的？？？？

里面的Adjust函数还是很有意思的！

✔️hooo! 在助教哥哥的帮助下算是解决了🌥

通过汇编发现，$H -> Data[H->Size+1] = DeleteMin(H);$ 这个语句它是先会通过H->Size给确定好数组的位置，然后再调用DeleteMin函数给它赋值，这也就导致了为什么第一个内容会丢掉了，其实并没有丢掉，只是赋值给了数组有效位置地后一个位置。这也解释了为什么前两天我运行时会出现奇怪的bug<好可惜，没能记录下来！>

所以改成

H->Data[H->Size] = DeleteMin(H);
或者
int item = DeleteMin(H);
H->Data[H->Size + 1] = item;

就可以了！！！

✔️我现在将上面的代码块修正了，原来的错误这里都有解释，然后在上面注释掉了！！！

然后给张测试图吧！

emmm,再给下这段代码的不同语句使用时地汇编代码吧！

小小小彩蛋！！！:🍀: 出卖一下我和助教哥哥地神奇对话