C语言实现优先队列：最大堆与最小堆排序

"这篇内容是关于优先队列的实现，主要使用了数组模拟堆排序的方法。堆是一种特殊的树形数据结构，通常分为最大堆和最小堆。最大堆中父节点的键值总是大于或等于其子节点的键值，而最小堆则相反，父节点的键值总是小于或等于子节点的键值。优先队列在此背景下，常用于处理具有优先级的任务，例如在图形算法中找到最短路径或在事件驱动模拟中管理事件等。" 在C语言中，优先队列通常通过堆来实现。在这个例子中，定义了一个结构体`SqList`来表示顺序存储的堆，包含`r[]`数组存储元素，`length`表示当前元素个数，`Maxsize`表示堆的最大容量。堆的类型定义为`HeapType`，它是`SqList`的别名。 代码首先包含了`malloc.h`、`stdio.h`和`stdlib.h`三个头文件，分别用于内存动态分配、标准输入输出和基本的库函数。 在优先队列的实现中，有四个关键函数： 1. `Max_HeapAdjust`：用于调整最大堆。当删除堆顶元素后，将最后一个元素放到堆顶并向下调整，确保其满足最大堆性质。函数接收堆引用`H`、待调整元素的索引`s`以及堆的最后一个非叶子节点的索引`m`作为参数。 2. `Min_HeapAdjust`：与`Max_HeapAdjust`类似，但用于调整最小堆。函数执行过程与最大堆调整相似，但保证的是最小堆的特性。 3. `Max_HeadSort`：对最大堆进行排序。首先从堆的中间位置开始，依次向上调整每个非叶子节点，保证堆的正确性。然后从堆顶开始，每次将堆顶元素（最大元素）与最后一个元素交换，然后调整堆，直到整个堆只剩下一个元素。 4. `Min_HeadSort`：最小堆的排序方法与`Max_HeadSort`类似，只是调整堆的逻辑不同。 这些函数可以用来创建和操作优先队列。例如，如果需要插入一个元素，可以先在数组的末尾添加，然后调用相应的调整函数保持堆的性质。若要删除最大（最小）元素，可以将堆顶元素与末尾元素交换，删除末尾元素，然后调用调整函数。 通过这种方式，我们可以高效地处理具有优先级的任务，因为堆的插入和删除操作时间复杂度为O(logn)，而排序的时间复杂度为O(nlogn)。这种实现方式适用于内存空间有限且需要频繁插入和删除元素的优先队列应用场景。