首页 ›存档› 技术 › 查看内容

图解堆算法、链表、栈与队列堆算法辨析栈与队列三种链表及其哨兵

2018-3-30 13:00 |来自: 互联网 412 0

摘要: 全世界只有3.14 %的人关注了数据与算法之美堆算法什么是堆堆（heap），是一类特殊的数据结构的统称。它通常被看作一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些 ...

全世界只有3.14 %的人关注了

数据与算法之美

堆算法

什么是堆

堆（heap），是一类特殊的数据结构的统称。它通常被看作一棵树的数组对象。在队列中，调度程序反复提取队列中的第一个作业并运行，因为实际情况中某些时间较短的任务却可能需要等待很长时间才能开始执行，或者某些不短小、但很重要的作业，同样应当拥有优先权。而堆就是为了解决此类问题而设计的数据结构。

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者近似完全二叉树，二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于任何一个子节点的键值时为最大堆，当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

为了更加形象，我们常用带数字的圆圈和线条来表示二叉堆等，但其实都是用数组来表示的。如果根节点在数组中的位置是1，第n个位置的子节点则分别在2n和2n 1位置上。

如下图所描的，第2个位置的子节点在4和5，第4个位置的子节点在8和9。所以我们获得父节点和子节点的方式如下：

PARENT(i)

1 return 小于或等于i/2的最大整数

LEFT-CHILD(i)

1 return 2i

RIGHT-CHILD(i)

1 return 2i 1

假定表示堆的数组为A，那么A.length通常给出数组元素的个数，A.heapsize表示有多少个堆元素存储在该数组中。这句话略带拗口，也就是说数组A[1...A.length]可能都有数据存放，但只有A[1...A.heapsize]中存放的数据才是堆中的有效数据。毫无疑问0≤A.heapsize≤A.length。

最大堆除了根以外所有结点i都满足：A[PARENT(i)]≥A[i]。

最小堆除了根以外所有结点i都满足：A[PARENT(i)]≤A[i]。

一个堆中结点的高度是该结点到叶借点最长简单路径上边的数目，如上图所示编号为4的结点的高度为1，编号为2的结点的高度为2，树的高度就是3。

包含n个元素的队可以看作一颗完全二叉树，那么该堆的高度是Θ(lgn)。