30,886
次編輯
變更
堆
,创建页面，内容为“{| class="wikitable" align="right" |- | style="background: #FF2400" align= center| '''<big>堆 </big>''' |- |<center><img src=https://img0.baidu.com/it/u=2081386718…”
{| class="wikitable" align="right"
|-
| style="background: #FF2400" align= center| '''<big>堆 </big>'''
|-
|<center><img src=https://img0.baidu.com/it/u=2081386718,604877992&fm=253&fmt=auto&app=138&f=JPEG?w=700&h=467 width="300"></center>
<small>[https://image.baidu.com/search/detail?ct=503316480&z=0&ipn=d&word=%E5%A0%86&step_word=&hs=0&pn=7&spn=0&di=7169026086108397569&pi=0&rn=1&tn=baiduimagedetail&is=0%2C0&istype=0&ie=utf-8&oe=utf-8&in=&cl=2&lm=-1&st=undefined&cs=1695093818%2C3538504488&os=827474566%2C2378510612&simid=4212301724%2C658746469&adpicid=0&lpn=0&ln=1858&fr=&fmq=1672305919155_R&fm=&ic=undefined&s=undefined&hd=undefined&latest=undefined©right=undefined&se=&sme=&tab=0&width=undefined&height=undefined&face=undefined&ist=&jit=&cg=&bdtype=0&oriquery=&objurl=https%3A%2F%2Fimg95.699pic.com%2Fxsj%2F14%2Fw1%2F3b.jpg!%2Ffw%2F700%2Fwatermark%2Furl%2FL3hzai93YXRlcl9kZXRhaWwyLnBuZw%2Falign%2Fsoutheast&fromurl=ippr_z2C%24qAzdH3FAzdH3Fxf3_z%26e3Bmllrtv_z%26e3Bv54AzdH3Fp7rtwgAzdH3F89o8nk_z%26e3Bip4s&gsm=1e&rpstart=0&rpnum=0&islist=&querylist=&nojc=undefined&dyTabStr=MCwzLDIsNCw2LDUsMSw3LDgsOQ%3D%3D 来自网络的图片]</small>
|-
|-
| align= light|
|}
堆(Heap)是计算机科学中一类特殊的数据[[结构]]，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。
==基本信息==
中文名；堆
外文名；heap
定 义；一类数据[[结构]]的统称
==释义==
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。[[常见]]的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(且)或者(), ()
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
==STL==
堆的STL包含于
头文件中。
堆的STL支持以下的基本操作:
1make_heap(first, last, comp);
建立一个空堆；
向堆中插入一个新元素；
1top_heap(first, last, comp);
获取当前堆顶元素的值；
1sort_heap(first, last, comp);
对当前堆进行排序；
==算法思想==
不必将值一个个地插入堆中，通过交换形成堆。假设一个小根堆的左、右子树都已是堆，并且根的元素名为 ，其左右子结点为 和 ，这种情况下，有两种可能：
（1） 并且 ，此时堆已完成；
（2） 或者 ，此时 应与两个子女中值较小的一个交换，结果得到一个堆，除非 仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将 “拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。
==筛选法==
首先将要排序的所有关键码放到一棵完全二叉树的各个结点中（这时的完全二叉树并不具备堆的特性）。显然，所有的结点 都没有子女结点，因此以这样的 为根的子树已经是堆，然后从 的结点Ki开始，逐步把以为根的子树排成堆，直到以K0为根的子树排成堆，就完成了建堆过程。
在考虑将以 为根的子树排成堆时，以 为根的子树已经是堆，所以这时如果有 和 ，则不必改变任何结点的位置，以 为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后 的值必定是原来 和 中较小的一个。假设 较小，将 与 交换位置，这样调整后，，并且以 为根的子树原来已经是堆，不必再作任何调整，只有以为根的子树由于的值已经发生变化（与交换了），所以有可能不满足堆的定义（当的左、右子树已经是堆）。这时可重复上述过程，考虑将以为根的子树排成堆。如此一层一层递推下去，最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。它就像过筛一样，把最小的关键码一层一层选择出来。<ref>[https://hanyu.baidu.com/zici/s?wd=%E5%A0%86&query=%E5%A0%86&srcid=28232&from=kg0 堆], 360国学 ,</ref>
=='''参考文献'''==
|-
| style="background: #FF2400" align= center| '''<big>堆 </big>'''
|-
|<center><img src=https://img0.baidu.com/it/u=2081386718,604877992&fm=253&fmt=auto&app=138&f=JPEG?w=700&h=467 width="300"></center>
<small>[https://image.baidu.com/search/detail?ct=503316480&z=0&ipn=d&word=%E5%A0%86&step_word=&hs=0&pn=7&spn=0&di=7169026086108397569&pi=0&rn=1&tn=baiduimagedetail&is=0%2C0&istype=0&ie=utf-8&oe=utf-8&in=&cl=2&lm=-1&st=undefined&cs=1695093818%2C3538504488&os=827474566%2C2378510612&simid=4212301724%2C658746469&adpicid=0&lpn=0&ln=1858&fr=&fmq=1672305919155_R&fm=&ic=undefined&s=undefined&hd=undefined&latest=undefined©right=undefined&se=&sme=&tab=0&width=undefined&height=undefined&face=undefined&ist=&jit=&cg=&bdtype=0&oriquery=&objurl=https%3A%2F%2Fimg95.699pic.com%2Fxsj%2F14%2Fw1%2F3b.jpg!%2Ffw%2F700%2Fwatermark%2Furl%2FL3hzai93YXRlcl9kZXRhaWwyLnBuZw%2Falign%2Fsoutheast&fromurl=ippr_z2C%24qAzdH3FAzdH3Fxf3_z%26e3Bmllrtv_z%26e3Bv54AzdH3Fp7rtwgAzdH3F89o8nk_z%26e3Bip4s&gsm=1e&rpstart=0&rpnum=0&islist=&querylist=&nojc=undefined&dyTabStr=MCwzLDIsNCw2LDUsMSw3LDgsOQ%3D%3D 来自网络的图片]</small>
|-
|-
| align= light|
|}
堆(Heap)是计算机科学中一类特殊的数据[[结构]]，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。
==基本信息==
中文名；堆
外文名；heap
定 义；一类数据[[结构]]的统称
==释义==
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。[[常见]]的堆有二叉堆、斐波那契堆等。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(且)或者(), ()
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
==STL==
堆的STL包含于
头文件中。
堆的STL支持以下的基本操作:
1make_heap(first, last, comp);
建立一个空堆；
向堆中插入一个新元素；
1top_heap(first, last, comp);
获取当前堆顶元素的值；
1sort_heap(first, last, comp);
对当前堆进行排序；
==算法思想==
不必将值一个个地插入堆中，通过交换形成堆。假设一个小根堆的左、右子树都已是堆，并且根的元素名为 ，其左右子结点为 和 ，这种情况下，有两种可能：
（1） 并且 ，此时堆已完成；
（2） 或者 ，此时 应与两个子女中值较小的一个交换，结果得到一个堆，除非 仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将 “拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。
==筛选法==
首先将要排序的所有关键码放到一棵完全二叉树的各个结点中（这时的完全二叉树并不具备堆的特性）。显然，所有的结点 都没有子女结点，因此以这样的 为根的子树已经是堆，然后从 的结点Ki开始，逐步把以为根的子树排成堆，直到以K0为根的子树排成堆，就完成了建堆过程。
在考虑将以 为根的子树排成堆时，以 为根的子树已经是堆，所以这时如果有 和 ，则不必改变任何结点的位置，以 为根的子树就已经是堆；否则就要适当调整子树中结点的位置以满足堆的定义。由于Ki的左、右子树都已经是堆，根结点是堆中最小的结点，所以调整后 的值必定是原来 和 中较小的一个。假设 较小，将 与 交换位置，这样调整后，，并且以 为根的子树原来已经是堆，不必再作任何调整，只有以为根的子树由于的值已经发生变化（与交换了），所以有可能不满足堆的定义（当的左、右子树已经是堆）。这时可重复上述过程，考虑将以为根的子树排成堆。如此一层一层递推下去，最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部，所以这个过程是不会反馈的。它就像过筛一样，把最小的关键码一层一层选择出来。<ref>[https://hanyu.baidu.com/zici/s?wd=%E5%A0%86&query=%E5%A0%86&srcid=28232&from=kg0 堆], 360国学 ,</ref>
=='''参考文献'''==