编辑代码

#include <stdio.h>
#include "windows.h"

typedef int E;

// 大顶堆（优先级队列）
struct MaxHeap {
    E *arr;
    int size;
    int capacity;
};

typedef struct MaxHeap *Heap;

// 初始化
BOOL initHead(Heap heap) {
    heap->capacity = 11;
    heap->size = 1;
    heap->arr = malloc(sizeof(E) * heap->capacity);
    return heap->arr != NULL;
}

// 插入
BOOL insert(Heap heap, E element) {
    if (heap->size == heap->capacity) return 0; //如果数组满了 则返回零
    int index = heap->size++;   // 确定插入元素index
    // 堆优化，确定插入元素正确位置，通过不断与小于自己的父元素交换位置
    while (index > 1 && heap->arr[index / 2] < element) {
        heap->arr[index] = heap->arr[index / 2];
        index /= 2;
    }
    // 确定正确位置，则插入
    heap->arr[index] = element;
    return 1;
}

// 堆删除，反向优化
E delete(Heap heap) {
    E Max = heap->arr[1], e = heap->arr[heap->size];  // 确定最大值，和最后面的值
    int index = 1;      //默认为1，会随着下面的while循环而改变
    // 这个while循环是确定 最后面的值的正确位置
    while (index * 2 < heap->size) {
        int child = index * 2;
        if (child < heap->size && heap->arr[child] < heap->arr[child + 1])  //确定较大的子节点
            child++;
        if (heap->arr[child] < e) break;    //如果较大的子节点不大于e 则跳出循环，e直接放在index值
        else
            heap->arr[index] = heap->arr[child];    //如果较大的子节点大于e，则子节点拉上来
        index = child;      // 较大的子节点继续循环，较大的子节点的index = child.index 继续循环确定位置
    }
    heap->arr[index] = e;   //插入到正确的位置
    return Max;     //返回删除值
}

int main() {
    struct MaxHeap heap;
    initHead(&heap);

    insert(&heap,5);
    insert(&heap,2);
    insert(&heap,3);
    insert(&heap,7);
    insert(&heap,6);
    insert(&heap,9);
    insert(&heap,11);

    for (int i = 1; i < 8; ++i) {
        printf("%d ", delete(&heap));
    }

}