導覽
近期變更
隨機頁面
新手上路
新頁面
優質條目評選
繁體
不转换
简体
繁體
18.118.226.2
登入
工具
閱讀
檢視原始碼
特殊頁面
頁面資訊
求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。
檢視 堆 的原始碼
←
堆
前往:
導覽
、
搜尋
由於下列原因,您沒有權限進行 編輯此頁面 的動作:
您請求的操作只有這個群組的使用者能使用:
用戶
您可以檢視並複製此頁面的原始碼。
{| 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> =='''参考文献'''== [[Category:800 語言、文學類]]
返回「
堆
」頁面