数据结构/最小堆和最大堆
以下是堆的一些定义
堆是一个数组，其中存在父子关系，并且子节点的索引是父节点索引的 2 倍或父节点索引的 2 倍加 1，子节点在父节点之后具有顺序，这是由堆的客户端程序注入的某种具体排序方案。在堆改变后，维护不变的顺序非常重要。有些人（Sedgewick 和 Wayne）创造了“上升”和“下降”这两个术语，其中维护不变性涉及将破坏不变性的项目向上移动到排序较低的子节点之上，然后下降到任何排序较高的子节点之下，因为可能有两个子节点，所以一个项目可以向上移动到排序较低的子节点之上，但仍然具有另一个排序较高的子节点。
堆是一种高效的半有序数据结构，用于存储可排序数据的集合。最小堆支持两种操作
INSERT(heap, element) element REMOVE_MIN(heap)
（我们讨论最小堆，但最小堆和最大堆之间没有真正的区别，除了比较的解释方式。）
本章将专门讨论二叉堆，尽管存在不同类型的堆。在大多数情况下，二叉堆和堆可以互换使用。堆可以看作是一棵树，具有父节点和子节点。堆和二叉树的主要区别在于堆属性。为了使一个数据结构被认为是堆，它必须满足以下条件（堆属性）
- 如果A 和B 是堆中的元素，并且B 是A 的子节点，则 key(A) ≤ key(B)。
（此属性适用于最小堆。最大堆的比较将被颠倒。）这告诉我们最小键将始终保留在顶部，而更大的值将在其下方。由于这个事实，堆被用来实现优先级队列，它允许快速访问具有最高优先级的项目。以下是一个最小堆的示例
堆是用一个从 1 到 N 索引的数组实现的，其中 N 是堆中元素的数量。
在任何时候，堆都必须满足堆属性
array[n] <= array[2*n] // parent element <= left child
和
array[n] <= array[2*n+1] // parent element <= right child
只要索引在数组边界内。
我们将证明array[1]是堆中的最小元素。我们通过观察如果其他元素小于第一个元素时的矛盾来证明它。假设array[i]是最小的第一个实例，其中对于所有j < i，array[j] > array[i]，并且i >= 2。但根据堆不变性，array[floor(i/2)] <= array[i]：这是一个矛盾。
因此，很容易计算MIN(heap)
MIN(heap)
return heap.array[1];
要删除最小元素，我们必须调整堆以填充heap.array[1]。这个过程称为渗透。基本上，我们将洞从节点 i 移动到节点2i 或2i+1。如果我们选择这两个节点中的最小值，堆不变性将得到保持；假设array[2i] < array[2i+1]。然后array[2i]将被移动到array[i]，在2i处留下一个洞，但移动后array[i] < array[2i+1]，因此堆不变性得到保持。在某些情况下，2i+1将超过数组边界，我们被迫渗透2i。在其他情况下，2i也在边界之外：在这种情况下，我们已经完成了。
因此，以下是最小堆的删除算法
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i + 1)
REMOVE_MIN(heap)
{
savemin=arr[1];
arr[1]=arr[--heapsize];
i=1;
while(i<heapsize){
minidx=i;
if(LEFT(i)<heapsize && arr[LEFT(i)] < arr[minidx])
minidx=LEFT(i);
if(RIGHT(i)<heapsize && arr[RIGHT(i)] < arr[minidx])
minidx=RIGHT(i);
if(minidx!=i){
swap(arr[i],arr[minidx]);
i=minidx;
}
else
break;
}
}
为什么这有效？
If there is only 1 element ,heapsize becomes 0, nothing in the array is valid. If there are 2 elements , one min and other max, you replace min with max. If there are 3 or more elements say n, you replace 0th element with n-1th element. The heap property is destroyed. Choose the 2 children of root and check which is the minimum. Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property. If no violations break.
INSERT 存在类似的策略：只需将元素附加到数组，然后通过交换修复堆不变性。例如，如果我们刚刚附加了元素 N，那么唯一可能的不变性违反涉及该元素，特别是如果，则这两个元素必须交换，现在唯一可能的不变性违反是在
![{\displaystyle array[floor(N/2)]>array[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24c556c36e19d6cdca1424cc3846013f01027bb6)
array[floor(N/4)] and array[floor(N/2)]
我们继续迭代，直到 N=1 或直到不变性得到满足。
INSERT(heap, element)
append(heap.array, element)
i = heap.array.length
while (i > 1)
{
if (heap.array[i/2] <= heap.array[i])
break;
swap(heap.array[i/2], heap.array[i]);
i /= 2;
}
Merge-heap: it would take two max/min heap and merge them and return a single heap. O(n) time. Make-heap: it would also be nice to describe the O(n) make-heap operation Heap sort: the structure can actually be used to efficiently sort arrays
Make-heap 将使用一个名为 heapify 的函数
//Element is a data structure//
Make-heap(Element Arr[],int size)
{
for(j=size/2;j>0;j--)
{
Heapify(Arr,size,j);
}
}
Heapify(Element Arr[],int size,int t)
{
L=2*t;
R=2*t+1;
if(L<size )
{
mix=minindex(Arr,L,t);
if(R<=size)
mix=minindex(Arr,R,mix);
}
else
mix=t;
if(mix!=t)
{
swap(mix,t);
Heapify(Arr,size,mix);
}
}
minindex 返回较小元素的索引
在 2009 年，一个较小的排序基准测试由 OzSort 赢得，该基准测试有一篇论文清楚地描述了如何使用优先级堆作为排序机来生成大型（内部）排序部分的合并部分。如果一个排序部分占用 M 个内存，排序问题是 k x M 个大，那么一次取 k 个部分中每个部分大小为 M/k 的连续部分，这样它们就适合 M 个内存（k * M/k = M），并为 k 个部分中的每个部分的第一个元素创建大小为 k 的优先级队列，以及当删除顶部元素并将其写入输出缓冲区时，从相应的部分取下一个元素。这意味着元素可能需要与它们来自的部分的标签相关联。当一个大小为 M/k 的部分用尽时，从存储在磁盘上的原始排序部分加载下一个大小为 M/k 的迷你部分。继续，直到磁盘上 k 个部分中的每个部分中的所有迷你部分都用尽。
（作为对磁盘操作延迟进行流水线的示例，存在双输出缓冲区，因此一旦一个输出缓冲区已满，一个缓冲区就会写入磁盘，而另一个缓冲区正在被填充。）
这篇论文表明，优先级堆比二叉树更直接，因为元素不断被删除，以及作为 k 路合并的排队机制而被添加，并且在对超过内部存储器存储的超大型数据集进行排序时具有实际应用。