维基百科

堆積：修订间差异

以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
EnderViking（留言 | 贡献）
856次编辑
小 内容扩充
 
（未显示28个用户的45个中间版本）
第1行：
{{Refimprove|time=2024-08-11T12:07:18+00:00}}
'''堆'''（英语：'''heap''')亦被称为：'''优先队列'''（英语：'''priority queue'''），是[[计算机科学]]中一类特殊的[[数据结构]]的统称。堆通常是一个可以被看做一棵树的数组对象。在[[队列]]中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。<ref name="定义">《数据结构与算法分析》 Mark Allen Weiss（美）第六章，优先队列（堆）。</ref>▼
{{NoteTA
<br />
|G1= IT
|1 = zh-cn:堆; zh-tw:堆積;
}}
{{For2|地理學的堆積|[[堆積作用]]|名稱相近的資料結構|[[堆栈]]（{{Lang|en|Stack}}）}}
{{For|動態記憶體分配的heap區段|动态内存分配}}
{{各地中文名
|cn = 堆
|tw = 堆積
}}
'''堆'''（{{Lang|en|Heap}}）是[[计算机科学]]中的一種特別的[[完全二叉树]]。若是滿足以下特性，即可稱為堆積：「給定堆積中任意[[節點]]P和C，若P是C的母節點，那麼P的值會小於等於（或大於等於）C的值」。若母節點的值恆'''小於等於'''子節點的值，此堆積稱為'''最小堆積'''（{{Lang|en|min heap}}）；反之，若母節點的值恆'''大於等於'''子節點的值，此堆積稱為'''最大堆積'''（{{Lang|en|max heap}}）。在堆積中最頂端的那一個節點，稱作'''根節點'''（{{Lang|en|root node}}），根節點本身沒有'''父節點'''（{{Lang|en|parent node}}）。
 
堆積始於{{le|J. W. J. Williams}}在1964年發表的'''堆積排序'''（{{Lang|en|heap sort}}），當時他提出了二元堆積樹作為此演算法的資料結構。
==逻辑定义==
n个元素序列{k<sub>1</sub>,k<sub>2</sub>...k<sub>i</sub>...k<sub>n</sub>},当且仅当满足下列关系时称之为堆：<br />
(k<sub>i</sub> <= k<sub>2i</sub>,k<sub>i</sub> <= k<sub>2i+1</sub>)或者(k<sub>i</sub> >= k<sub>2i</sub>,k<sub>i</sub> >= k<sub>2i+1</sub>),
(i = 1,2,3,4...n/2)
 
==性质==
堆的实现通过构造'''二叉堆'''（binary heap），实为[[二叉树]]的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。
* 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（'''堆序性'''）。
* 堆总是一棵[[完全二叉树|完全树]]。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
将根节点最大的堆叫做'''最大堆'''或'''大根堆'''，根节点最小的堆叫做'''最小堆'''或'''小根堆。常见的堆有[[二叉堆]]、[[斐波那契堆]]等'''。
 
堆有許多種進階類型包含了適合製作雙端佇列的[[最大—最小堆|最大—最小堆積]]及製作優先權佇列的[[斐波那契堆|斐波那契堆積]]等。
 
== 支持的基本操作 ==
 
堆支持以下的基本:
{| class="wikitable"
* build：建立一个空堆；
|-
* insert：向堆中插入一个新元素；▼
! 操作 !! 描述 !! [[时间复杂度]]
* update：将新元素提升使其符合堆的性质；▼
|-
* get：获取当前堆顶元素的值；▼
| build || 採用[[罗伯特·弗洛伊德|羅伯特·弗洛伊德]]提出的較快方式建立堆 || <math>O(n)</math>
* delete：删除堆顶元素；
|-
* heapify：使删除堆顶元素的堆再次成为堆。▼
▲*| insert || insert：向堆中插入一个新元素； || <math>O(\log n)</math>
|-
▲*| update || update：将新元素提升使其符合堆的性质； || <math>O(\log n)</math>
|-
▲*| get || get：获取当前堆顶元素的值； || <math>O(1)</math>
|-
| delete || 删除堆顶元素 || <math>O(\log n)</math>
|-
▲*| heapify || heapify：使删除堆顶元素的堆再次成为堆。 || <math>O(\log n)</math>
|}
 
某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。
 
[https://gallery.selfboot.cn/zh/algorithms/heap 堆的在线可视化页面]提供了多种堆操作的可视化演示。可以通过界面上的切换按钮在大根堆和小根堆之间自由切换，切换时系统会自动重新构建整个堆结构。<ref>[https://gallery.selfboot.cn/zh/algorithms/heap 堆的在线可视化页面]: 支持堆操作的可视化演示</ref>
==例程==▼
为将元素</code>X</code>插入堆中，找到空闲位置，建立一个空穴，若满足'''堆序性'''（英文：'''heap order'''），则插入完成；否则将[[二叉树|父节点]]元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做'''上滤'''（percolate up）。<ref name="定义" />▼
<syntaxhighlight lang="c">▼
void
Insert( ElementType X, PriorityQueue H )▼
{
int i;▼
 
可以在输入框中输入数字并点击"插入节点"按钮，就能观察新节点如何通过上浮（heapify up）操作找到其正确位置。
if( IsFull(H) )▼
 
{
当点击"删除根节点"按钮时，可以看到堆顶元素被移除，以及最后一个节点如何通过下沉（heapify down）操作重建堆的平衡。删除的节点会在右侧短暂显示，随后会消失。
printf( "Queue is full.\n" );▼
 
此外，该页面还提供了随机初始化功能，可以快速生成一个包含10到50个随机数值的新堆，方便进行各种测试和观察。
 
▲==示例程代码==
▲为将元素</code>X</code>插入堆中，找到空闲位置，建立一个空穴，若满足'''堆序性'''（英文：'''heap order'''），则插入完成；否则将[[二叉树|父节点]]元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做'''上滤'''（percolate up）。<ref name="定义">《数据结构与算法分析》Mark Allen Weiss（美）第六章，优先队列（堆）。</ref>
▲<syntaxhighlight lang="c" style="overflow:hidden" line="1">
▲void Insert( ElementType X, PriorityQueue H ) {
▲ int i;
▲ if( (IsFull(H) ) {
▲ printf( "Queue is full.\n" );
return;
}
for (i = ++H->Size; H->Element[i / 2] > X; i /= 2)
 
for( i = ++H->Size; H->ElementElements[i/2] = H-> X; Elements[i /= 2 )];
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = X;
}
第45行 ⟶ 第68行：
 
<code>DeleteMin</code>，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作'''下滤'''。
<syntaxhighlight lang="c" style="overflow:hidden" line="1">
ElementType DeleteMin(PriorityQueue H) {
DeleteMin( PriorityQueue H )
{
int i, Child;
ElementType MinElement, LastElement;
if ( IsEmpty( H )) ){▼
 
printf( "Queue is empty.\n" );▼
▲ if( IsEmpty( H ) )
{
▲ printf( "Queue is empty.\n" );
return H->Elements[0];
}
MinElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for (i = 1; if(i Child* 2 !<= H->Size; &&i = H->Elements[Child+1]) {▼
 
for( i = 1; i*2// <=Find H->Size;smaller i = Child )child.
Child = i * 2;
{
/*if Find(Child smaller!= child.H->Size */&& H->Elements[Child + 1]
Child = i*2; < H->Elements[Child])
▲ if( Child != H->Size && H->Elements[Child+1]
< H->Elements[Child] )
Child++;
// Percolate one level.
 
/*if Perlocate(LastElement one> level. */H->Elements[Child])
if( LastElement > H->Elements[Child] )
H->Elements[i] = H->Elements[Child];
else
第85行 ⟶ 第101行：
=== 事件模拟 ===
主要运用堆的排序以选择优先。
 
=== 優先權佇列 ===
▲'''堆'''（英语：'''heap''')亦被称为：'''优先队列'''（英语：'''priority queue'''），是[[计算机科学]]中一类特殊的[[数据结构]]的统称。堆通常是一个可以被看做一棵树的数组对象。在[[队列]]中，调度程序反复提取队列中第一个作业并运行，因而为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种最佳数据结构。<ref name="定义">《数据结构与算法分析》 Mark Allen Weiss（美）第六章，优先队列（堆）。</ref>
 
=== 戴克斯特拉演算法 ===
在[[戴克斯特拉算法|戴克斯特拉演算法]]中使用[[斐波那契堆|斐波那契堆積]]或二元堆可使得佇列的操作更為快速。
 
==参考==
第92行 ⟶ 第114行：
* [[二叉堆]]
* [[二项式堆]]
* [[最大小-最小大堆]]
* [[斐波纳契堆]]
* [[数据结构]]
 
{{-}}
{{Data structures}}
{{计算机科学中的树}}
 
[[Category:数据结构|D]]
[[Category:树结构]]
[[Category:堆| ]]
检索自“https://zh.wikipedia.org/wiki/堆積”