赞
踩
堆的概念与算法
我们先来了解堆的概念,然后介绍堆的一些主要算法。
基本概念
堆首先是一棵二叉树,但它是完全二叉树 。
什么是完全二叉树呢?
我们先来看另一个相似的概念:满二叉树。满二叉树是指除了最后一层外,每个节点都有两个孩子,而最后一层都是叶子节点,都没有孩子。
满二叉树一定是完全二叉树,但完全二叉树不要求最后一层是满的,但如果不满,则要求所有节点必须集中在最左边,从左到右是连续的,中间不能有空的。比如,图11-2所示几棵二叉树都是完全二叉树。
如果编号为i,则父节点编号即为i/2,左孩子编号即为2×i,右孩子编号即为2×i+1。比如,对于5号节点,父节点为5/2即2,左孩子为2×5即10,右孩子为2×5+1即11。
这个特点为什么重要呢?
它使得逻辑概念上的二叉树可以方便地存储到数组中,
数组中的元素索引就对应节点的编号,树中的父子关系通过其索引关系隐含维持,不需要单独保持。
这种存储二叉树的方法与之前介绍的TreeMap是不一样的。在TreeMap中,有一个单独的内部类Entry,Entry有三个引用,分别指向父节点、左孩子、右孩子。使用数组存储的优点是节省空间,而且访问效率高。堆逻辑概念上是一棵完全二叉树,而物理存储上使用数组,还有一定的顺序要求。
之前介绍过排序二叉树。排序二叉树是完全有序的,每个节点都有确定的前驱和后继,而且不能有重复元素。与排序二叉树不同,在堆中,可以有重复元素,元素间不是完全有序的,但对于父子节点之间,有一定的顺序要求。根据顺序分为两种堆:一种是最大堆,另一种是最小堆 。
最大堆是指每个节点都不大于其父节点。这样,对每个父节点,一定不小于其所有孩子节点,而根节点就是所有节点中最大的,对每个子树,子树的根也是子树所有节点中最大的。最小堆与最大堆正好相反,每个节点都不小于其父节点。这样,对每个父节点,一定不大于其所有孩子节点,而根节点就是所有节点中最小的,对每个子树,子树的根也是子树所有节点中最小的。
总结来说,逻辑概念上,堆是完全二叉树,父子节点间有特定顺序,分为最大堆和最小堆,最大堆根是最大的,最小堆根是最小的,堆使用数组进行物理存储。
为什么堆可以高效地解决之前我们说的问题呢?
在回答之前,我们需要先看下,如何在堆上进行数据的基本操作,在操作过程中如何保持堆的属性不变。
堆的算法
下面,我们介绍如何在堆上进行数据的基本操作。最大堆和最小堆的算法是类似的,我们以最小堆来说明。先来看如何添加元素。
1.添加元素
如果堆为空,则直接添加一个根就行了。我们假定已经有一个堆,要在其中添加元素,基本步骤为:
1)添加元素到最后位置。
2)与父节点比较,如果大于等于父节点,则满足堆的性质,结束,否则与父节点进行交换,然后再与父节点比较和交换,直到父节点为空或者大于等于父节点。
堆的算法示例:添加元素前的初始结构
添加元素3,第一步后,
堆的算法示例:添加元素3第一步后的结构3小于父节点8,不满足最小堆的性质,所以与父节点交换,
交换后,3还是小于父节点6,所以继续交换,
交换后,3还是小于父节点,也是根节点4,继续交换,
至此,调整结束,树保持了堆的性质。
从以上过程可以看出,添加一个元素,需要比较和交换的次数最多为树的高度,即log2(N),N为节点数。这种自底向上比较、交换,使得树重新满足堆的性质的过程,我们称为向上调整(siftup)。
2.从头部删除元素
在队列中,一般是从头部删除元素,Java中用堆实现优先级队列。下面介绍如何在堆中删除头部,其基本步骤为:
1)用最后一个元素替换头部元素,并删掉最后一个元素;
2)将新的头部与两个孩子节点中较小的比较,如果不大于该孩子节点,则满足堆的性质,结束,否则与较小的孩子节点进行交换,交换后,再与较小的孩子节点比较和交换,一直到没有孩子节点,或者不大于两个孩子节点。这个过程称为向下调整(siftdown)。
想要了解更多Java基础知识,点击下方链接和小编一起学习java吧,此视频教程为初学者而著,零基础入门篇!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。