计算机程序的思维逻辑 (45) - 神奇的堆
|
副标题[/!--empirenews.page--]
前面几节介绍了Java中的基本容器类，每个容器类背后都有一种数据结构，ArrayList是动态数组，LinkedList是链表，HashMap/HashSet是哈希表，TreeMap/TreeSet是红黑树，本节介绍另一种数据结构 - 堆。 引入堆 之前我们提到过堆，那里，堆指的是内存中的区域，保存动态分配的对象，与栈相对应。这里的堆是一种数据结构，与内存区域和分配无关。 堆是什么结构呢？这个我们待会再细看。我们先来说明，堆有什么用？为什么要介绍它？ 堆可以非常高效方便的解决很多问题，比如说：
堆还可以实现排序，称之为堆排序，不过有比它更好的排序算法，所以，我们就不介绍其在排序中的应用了。 Java容器中有一个类PriorityQueue，就表示优先级队列，它实现了堆，下节我们会详细介绍。关于后面两个问题，它们是如何使用堆高效解决的，我们会在接下来的几节中用代码实现并详细解释。 说了这么多好处，堆到底是什么呢？ 堆的概念 完全二叉树 堆首先是一颗二叉树，但它是完全二叉树。什么是完全二叉树呢？我们先来看另一个相似的概念，满二叉树。 满二叉树是指，除了最后一层外，每个节点都有两个孩子，而最后一层都是叶子节点，都没有孩子。比如，下图两个二叉树都是满二叉树。
编号与数组存储 在完全二叉树中，可以给每个节点一个编号，编号从1开始连续递增，从上到下，从左到右，如下图所示：
这个特点为什么重要呢？它使得逻辑概念上的二叉树可以方便的存储到数组中，数组中的元素索引就对应节点的编号，树中的父子关系通过其索引关系隐含维持，不需要单独保持。比如说，上图中的逻辑二叉树，保存到数组中，其结构为：
父子关系是隐含的，比如对于第5个元素13，其父节点就是第2个元素15，左孩子就是第10个元素7，右孩子就是第11个元素4。 这种存储二叉树的方法与之前介绍的TreeMap是不一样的，在TreeMap中，有一个单独的内部类Entry，Entry有三个引用，分别指向父节点、左孩子、右孩子。 使用数组存储，优点是很明显的，节省空间，访问效率高。 最大堆/最小堆 堆逻辑概念上是一颗完全二叉树，而物理存储上使用数组，除了这两点，堆还有一定的顺序要求。 之前介绍过排序二叉树，排序二叉树是完全有序的，每个节点都有确定的前驱和后继，而且不能有重复元素。 与排序二叉树不同，在堆中，可以有重复元素，元素间不是完全有序的，但对于父子节点之间，有一定的顺序要求，根据顺序分为两种堆，一种是最大堆，另一种是最小堆。 最大堆是指，每个节点都不大于其父节点。这样，对每个父节点，一定不小于其所有孩子节点，而根节点就是所有节点中最大的，对每个子树，子树的根也是子树所有节点中最大的。 最小堆与最大堆正好相反，每个节点都不小于其父节点。这样，对每个父节点，一定不大于其所有孩子节点，而根节点就是所有节点中最小的，对每个子树，子树的根也是子树所有节点中最小的。 我们看下图示：
总结来说，逻辑概念上，堆是完全二叉树，父子节点间有特定顺序，分为最大堆和最小堆，最大堆根是最大的，最小堆根是最小的，堆使用数组进行物理存储。 这个数据结构为什么就可以高效的解决之前我们说的问题呢？在回答之前，我们需要先看下，如何在堆上进行数据的基本操作，在操作过程中，如何保持堆的属性不变。 堆的算法 下面，我们来看下，如何在堆上进行数据的基本操作。最大堆和最小堆的算法是类似的，我们以最小堆来说明。先来看如何添加元素。 添加元素 如果堆为空，则直接添加一个根就行了。我们假定已经有一个堆了，要在其中添加元素。基本步骤为：
我们来看个例子。下面是初始结构：
从以上过程可以看出，添加一个元素，需要比较和交换的次数最多为树的高度，即log2(N)，N为节点数。 这种自低向上比较、交换，使得树重新满足堆的性质的过程，我们称之为siftup。 从头部删除元素 （编辑：淮北站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
