打开主菜单

求真百科

来自网络的图片

堆(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的左、右子树都已经是堆,根结点是堆中最小的结点,所以调整后 的值必定是原来 和 中较小的一个。假设 较小,将 与 交换位置,这样调整后,,并且以 为根的子树原来已经是堆,不必再作任何调整,只有以为根的子树由于的值已经发生变化(与交换了),所以有可能不满足堆的定义(当的左、右子树已经是堆)。这时可重复上述过程,考虑将以为根的子树排成堆。如此一层一层递推下去,最多可以一直进行到树叶。由于每步都保证将子树中最小的结点交换到子树的根部,所以这个过程是不会反馈的。它就像过筛一样,把最小的关键码一层一层选择出来。[1]

参考文献

  1. , 360国学 ,